java - 如何衡量该算法的时间复杂度(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 来指代紧界。