如何衡量该算法的时间复杂度（Big-O）？

Question

我正在尝试测量以下算法的大 O 复杂度：

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;
}

现在根据我的理解，

if (arr[i] > arr[j])
                sum += arr[i];

具有 O(1) 的大 O，因为它是常数并且什么也没有发生，尽管我很难辨别它的大 O 表示法，但听起来它的 for 循环。我假设

for (int j=1; j<arr.length; j = j*2) {
         if (arr[i] > arr[j])
            sum += arr[i];
}

是一个线性函数 O(n)，因为 j 可能为 1，但它在 O(2n) 处以线性方式上升，也就是 O(n)。那么整个算法不就是 O(n^2) 吗？显然我在 MOOC 考试中没有正确回答问题。谢谢！

Answer 1

is a linear function O(n) because j maybe 1 but it's going up in a linear fashion at O(2n) which is just O(n). So wouldn't the entire algorithm be O(n^2). Apparently I didn't answer the question correctly on a MOOC exam. Thanks!

它不是线性上升，而是呈指数上升，因为每次迭代都将 j 乘以 2。

j = 1, 2, 4, 8, 16, 32, ..., 2^k < n
2^k < n | apply log base 2 => k < log_2 n => k = O(log n)

所以第二个循环只执行了O(log n)次，使得整个代码序列O(n log n).

严格来说，O(n^2)也是正确答案，因为如果O(n log n)是上限，那么O(n^2)也是。然而 n^2 的 Big Theta 并不正确，人们通常也使用 Big-Oh 来指代紧界。

Answer 2

Big-O 的关键是寻找循环，所以你的关键部分在这里：

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];
   }
}

外层循环执行 N 次，因为它以 1 的增量从 0 到 N。

内部循环在每次外部迭代中执行 Log N 次，因为它从 1 到 N 以指数方式执行。（我怀疑你错过的部分是循环中的迭代器：j = j*2。这使得 J 呈指数增长，而不是线性增长，因此它将在 log-base-2 时间内达到 N。如果它是 +2，而不是 *2)

内部的 if 对于 Big-O 无关紧要，因为它只增加了一个系数。

因此，只需将循环的阶数相乘即可：N * Log N = N Log N

如何衡量该算法的时间复杂度（Big-O）？

How to measure the time-complexity (Big-O) of this algorithm?

java

algorithm

big-o

time-complexity

asymptotic-complexity