英文:
What is the Big-O class of the following nested for loop?
问题
我需要帮助弄清楚为什么下面这段 Java 代码片段的时间复杂度是 O(nlogn)，而不是 O(n^2)。能帮忙解释一下吗？
int sumSome(int[] arr){
int sum = 0;
for (int i=0; i<arr.length; i++) {
for (int j=1; j<arr.length; j = j*2) {
if (arr[i] > arr[j])
sum += arr[i];
}
}
return sum;
}
英文:
I need help figuring out why the following code-snippet in Java is O(nlogn) instead of O(n^2). Any help please?
int sumSome(int[] arr){
int sum = 0;
for (int i=0; i<arr.length; i++) {
for (int j=1; j<arr.length; j = j*2) {
if (arr[i] > arr[j])
sum += arr[i];
}
}
return sum;
}
答案1
得分: 5
可能有助于考虑一个通用的数字区间，比如 1 到 100。
- 如果你逐个循环遍历这个区间，循环的时间复杂度为 O(n)。
- 如果你按照任意线性步长循环遍历，比如一次2个或一次10个，循环的时间复杂度仍然是 O(n/2)，O(n/10)，等等，最终简化为 O(n)。
然而，如果循环步长的大小每次通过循环时都发生变化，你会得到不同的结果：
- 如果你通过每次加倍步长来循环遍历该范围（1、2、4、8、16、32、64），在到达结尾之前，你将只运行循环7次。这是步长呈指数增长，对应于循环次数的对数增长：1 + 以2为底的log(100)（向下取整），这简化为 O(log n)。
- 如果你每次将步长乘以3（1、3、9、27、81），以以3为底的log(100)循环次数运行，仍然简化为 O(log n)。依此类推。
因此在你的示例中，外部循环的时间复杂度为 O(n)，乘以内部循环的时间复杂度 O(log n)，得出总的时间复杂度为 O(n * log n)。
关于不同时间复杂度的优秀示例可以在这个答案中找到。
英文:
It may be helpful to think of a general number interval, say 1 to 100.
- If you loop through that interval one by one, the loop will be O(n)
- If you loop through it by any linear step size, like 2 at a time or 10 at a time, the loop will be O(n/2), O(n/10), etc., which still simplifies to O(n).
However, if the size of the loop step changes each time through the loop, you get different results:
- If you loop through the range while doubling the step each time (1, 2, 4, 8, 16, 32, 64), you will end up running the loop only 7 times before reaching the end. This is exponential growth of the step size, which corresponds to a logarithmic number of times through the loop: 1 + log(100) with log base 2 (rounded down), which simplifies to O(log n).
- If you multiply your step size by 3 each time (1, 3, 9, 27, 81), it will loop 1 + log(100) times with log base 3, which still simplifies to O(log n). And so on.
So in your example, you have your outer loop O(n) times your inner loop O(log n), leading to a combined O(n * log n).
Great examples of different time complexities can be found in this answer.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论