我需要帮助弄清楚为什么下面的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;
}
考虑一个通用的数字区间可能会有所帮助，比如说1到100。
- 如果你一个接一个地循环通过这个区间，循环将是O(n(
- 如果你按任何线性步长循环，比如一次2个或一次10个，循环将是O(n/2(、O(n/10(等，这仍然简化为O(n(
然而，如果循环步骤的大小在循环中每次都发生变化，则会得到不同的结果：
- 如果您在每次将步长加倍(1、2、4、8、16、32、64(的同时循环整个范围，那么在到达终点之前，您将只运行循环7次。这是步长的指数增长，对应于循环的对数次数：1+log(100(，对数基数为2(向下取整(，简化为O(logn(
- 如果每次将步长乘以3(1，3，9，27，81(，它将以logbase 3循环1+log(100(次，这仍然简化为O(logn(。等等
因此，在您的示例中，您的外循环O(n(乘以内循环O(logn(，得到组合的O(n*logn(。
在这个答案中可以找到不同时间复杂性的伟大例子。