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

Question

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

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

我使用什么策略来找到这段代码的 Big 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)。