英文:
Outer loop linear, inner loop logarithmic, complexity analysis
问题
以下是代码的时间复杂度，O(logn) 或 O(nlogn)？
int i = 1;
while (i <= n) {
int j = i;
while (j > 0) {
j = j / 2;
}
i++;
}
英文:
What is the complexity for the following piece of code, O(logn) or O(nlogn)?
int i=1;
while (i<= n) {
int j = i;
while (j > 0) {
j = j/2;
}
i++;
}
I asked chatgpt and sometimes it says O(logn) and sometimes O(nlogn). The argument for O(logn) is that the inner loop dominates the number of iterations and that it should be taken, and the argument for O(nlogn) (which I find more reasonable) is that this is the sum of logarithms from 1 to n, which is logn!, which can be approximated to O(nlogn). I also saw this stackoverflow question and one of the answers is O(nlogn) and the other O(logn).
答案1
得分: 1
以下是翻译好的部分：
-
"It is O(n logn)."
- "这是 O(n logn)。"
-
"It is easy to disprove O(logn): The outer loop executes exactly n times, so the algorithm must be Ω(n). At this point it doesn't matter even if the inner loop would execute 0 times because it is still a constant-time operation."
- "很容易证明不是 O(logn)：外循环恰好执行 n 次，因此算法必须是 Ω(n)。在这一点上，即使内循环执行 0 次也无关紧要，因为它仍然是一个常数时间操作。"
-
"Proving that it is indeed O(n logn) is a bit more tricky and involves some math, but that's not really what you are asking so I won't get into that. But in cases like this, you can perform a very easy sanity check, by just counting the number of iterations the inner loop will perform:"
- "证明它确实是 O(n logn) 有点棘手，涉及一些数学，但这并不是你问的问题，所以我不会深入讨论。但在这种情况下，你可以进行一个非常简单的合理性检查，只需计算内循环将执行的迭代次数："
-
代码部分不翻译。
-
"The value of counter for different inputs of n will answer your question in practice, even if it's not a formal proof."
- "对于不同的 n 输入，计数器的值将在实践中回答你的问题，即使它不是正式的证明。"
-
"As for ChatGPT, it is important to remember that it's far from an authority, so I would disregard it and not think too much about how it might have picked up that argument about O(log n). If we must speculate, then I suppose ChatGPT might have learned that argument from other contexts, such as when you have two parallel (not nested) loops where one takes more time than the other. Then, the slower one will dominate and let you ignore the faster one. But obviously that argument is applied incorrectly here. So yes, your own logic seems fine to me."
- "至于ChatGPT，重要的是要记住它远非权威，因此我建议忽略它，不要过多考虑它是如何得出关于 O(log n) 的论点的。如果我们必须猜测，那么我认为ChatGPT可能从其他上下文中学到了这个论点，例如当你有两个并行（不是嵌套的）循环，其中一个花费的时间比另一个多。然后，较慢的循环将主导，并允许你忽略较快的循环。但显然，这个论点在这里被错误地应用。所以是的，你自己的逻辑对我来说是正确的。"
英文:
It is O(n logn).
It is easy to disprove O(logn): The outer loop executes exactly n times, so the algorithm must be Ω(n). At this point it doesn't matter even if the inner loop would execute 0 times because it is still a constant-time operation.
Proving that it is indeed O(n logn) is a bit more tricky and involves some math, but that's not really what you are asking so I won't get into that. But in cases like this, you can perform a very easy sanity check, by just counting the number of iterations the inner loop will perform:
int i=1;
counter = 0;
while (i<= n) {
int j = i;
while (j > 0) {
j = j/2;
counter++;
}
i++;
}
The value of counter for different inputs of n will answer your question in practice, even if it's not a formal proof.
As for ChatGPT, it is important to remember that it's far from an authority, so I would disregard it and not think too much about how it might have picked up that argument about O(log n). If we must speculate, then I suppose ChatGPT might have learned that argument from other contexts, such as when you have two parallel (not nested) loops where one takes more time than the other. Then, the slower one will dominate and let you ignore the faster one. But obviously that argument is applied incorrectly here. So yes, your own logic seems fine to me.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论