for-loop - 计算嵌套 for 循环的复杂度

Question

我想计算这个嵌套 for 循环的复杂度：

s = 0;
for(i=1; i<=n; i*=2)
   for(j=1; j<=i; j*=2)
      s++;

我使用什么策略来找出这段代码的大 O 复杂度？

Answer 1

外循环经过 1, 2, 4, 8, ... n，这需要 O(lg n ) 步，因为你只能加倍 O(lg n ) 次，直到你击中n。

内循环也是如此。它只上升到i，但是在外循环的最后一次迭代中，i达到了它的最大值，又是n，所以这也是 O(lg n )。

将其放在一起给出 O((lg n )²) 的上限，通常缩写为 O(lg² n )。

Answer 2

自己获得答案的策略

将不同的 n 值代入方程，并绘制循环最里面部分运行次数的图表：

s = 0;
for(i=1; i<=n; i*=2)
  for(j=1; j<=i; j*=2)
    s++;

像这样的东西：

n     num_times_inner_loop_part_runs
1     1
2     3
3     3
4     6
5     6
6     6
7     6
8     10
9     10
...
15    10
16    15
...
31    15
32    21

您可以使用如下程序获取这些数据点：

int n = 9;  //change this n
int counter = 0;
for(i=1; i<=n; i*=2){
  for(j=1; j<=i; j*=2){
    s++;
    counter++;
  }
}
cout << "counter is: " <<  counter << endl;

在 X/Y 坐标平面上绘制num_times_inner_loop_part运行图，您会看到一条曲线。

命名最接近的曲线。在这种情况下，它是X = (log(Y)^2)

如果您绘制数据 和X = (log(Y)^2)，您会发现它们应该相互重叠。

因此，这个函数的复杂度O((log(n))^2)是O(n)

Answer 3

这段代码的时间分析：

Answer 4

您的算法时间复杂度可以正式描述如下：

本文档（最后一张幻灯片）可能对您非常有用。