大 O 的简单复杂度并不总是线性的？
我确信你们大多数人都知道，如果函数输入大小为 n，嵌套循环的复杂度为 O(n^2)
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
...
}
}
我认为通过类似的参数，这很相似，但我不确定有人能确认吗？
for(int i = 0, max = n*n; i < max; i++{
...
}
如果是这样，我猜想除了递归和子例程之外，有些代码的大 O 映射并不是立即显而易见的。
I'm sure most of you know that a nested loop has O(n^2) complexity if the function input size is n
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
...
}
}
I think that this is similar, by a analogous argument, but i'm not sure can anyone confirm?
for(int i = 0, max = n*n; i < max; i++{
...
}
If so i guess that there is some kinds of code whose big O mapping is not immediately obvious besides recursion and subroutines.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
基本的简单循环始终为 O(m)，其中 m 是迭代的上限。但你的 m 实际上是 n*n，所以它是 O(n^2)。
Your basic simple loop is always O(m) where m is the upper bound on the iterations. But your m is really n*n, so it's O(n^2).
如果 m = n^2，那么“简单 for”在 m 中肯定是线性的。如果您想争论这是 n^2，请继续。
Big-O 表示法在这里对运算进行计数。如果您正在执行其中的 n^2 个操作，我不确定报告 n^2 的总和会告诉您什么，因为您正在执行 m 个操作。
你的建议对我来说没有意义。该金额的真实名称具有误导性。正确的说法是 O(m)。
If m = n^2, then a "simple for" is certainly linear in m. If you'd like to argue that this is n^2, please go ahead.
The Big-O notation is counting operations here. If you're performing n^2 of them, I'm not sure what reporting the sum as n^2 tells you, because you're performing m operations.
Your proposal doesn't make sense to me. It's misleading about the true name of that sum. The correct way to say it is O(m).
取决于你所说的“简单”是什么意思。大小为 n 的排序数组中的除以二搜索也可以编写为非嵌套 for 循环，但需要 O(log(n)) 时间。正如您所说，从 0 到 n*n 的 for 循环将在 O(n*n) 时间内执行。
是的，有些代码的运行时间不是很明显。更重要的是，有些代码的效果甚至目的也不是立即显而易见的:)
Depends on what do you mean by "simple". A divide-by-two search in a sorted array of size n can be written as a non-nested for loop, too, but it would have O(log(n)) time. And like you rightly said, a for loop from 0 to
n*nwould execute in O(n*n) time.Yes, there are codes where running time is not immediately obvious. Even more, there's code out there where the effect and even purpose is not immediately obvious, too :)
它仍然是 O(n) - 只不过在这种情况下你的“n”是“n*n”。您只是增加了 n 的值，而不是循环的复杂性。
It's still O(n) - except that your "n" in this case is "n*n". You've simply increased the value of n - not the complexity of the loop.