Big O - 时间复杂度令人费解的 while 循环

Question

作为一个时间复杂度的例子（让我耳目一新），我试图解决找到以下算法的运行ning 时间（在 n 方面）：

for (i=1; i <= n; i++) {      //O(n)
  k = 1;
  for (j=1; j <= i; j++) {    //O(n)
    k = 2*k;
  }
  j = k*k;
  while (j > 1) {             //O(..?)
    j = j / 2;
  }
}

我理解前两个 for 循环加起来需要 O(n^2)，但是我对如何找到 while 循环的运行ning 时间有点困惑。虽然我知道 while 循环运行s 第一次执行两次，然后是 4 次，然后是 6 次……都是 2 的倍数。这是否会使它成为运行 O(nlog(n)) 次？

Answer 1

重复除法为log_2(j)，与log(j) / log(2)相同。 log(2) 是常量，所以写成 log(j).

因为 O(log(n)) 与 O(n) 循环的深度相同，而 O(n) 循环使 O(log(n)) 循环相形见绌，因此两者合并需要 O(n) 时间。

最终时间复杂度为O(n^2)。

Answer 2

对于 i 的每个值，我们执行两个循环。

第一个对每个i值执行i次第三个，j从2^i开始，除以2成功，所以也执行了i次。

总共有 O(1+2+..+n) ~ O(n(n+1)/2) ~ O(n^2)

Big O - 时间复杂度令人费解的 while 循环

Big O - Time Complexity puzzling for while loops

big-o

time-complexity

while-loop