以下嵌套 for 循环的 Big-O 类是什么？

Question

我需要帮助弄清楚为什么 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;
}

Answer 1

考虑一个通用的数字区间可能会有所帮助，比如1 到 100。

• 如果你一个一个循环遍历那个间隔，循环将是 O(n)
• 如果您以任何线性步长循环遍历它，例如一次 2 或一次 10，则循环将是 O(n/2)、O(n/10) 等，这仍然简化为 O(n ）。

但是，如果每次通过 loop 时循环步长的大小都发生变化，则会得到不同的结果：

• 如果您在每次将步长加倍（1、2、4、8、16、32、64）的同时循环遍历范围，那么在到达终点之前，您最终只会运行循环 7 次。这是步长的指数增长，它对应于循环中的对数次数：1 + log(100) 以 log 为底 2（向下取整），简化为 O(log n)。
• 如果您每次将步长乘以 3 (1, 3, 9, 27, 81)，它将以对数基数 3 循环 1 + log(100) 次，这仍然简化为 O(log n)。等等。

所以在你的例子中，你的外循环 O(n) 乘以你的内循环 O(log n)，导致组合 O(n * log n)。

在这个答案中可以找到不同时间复杂度的很好的例子。