求i=i*i迭代的循环时间复杂度及正式推导方法

先看你给出的代码：

i=2;
while(i < n) {
   i = i*i;
   //O(1) complexity here
}

我们一步步推导它的时间复杂度：

• 先列出每次循环后i的取值规律：

  • 初始状态（未进入循环）：i = 2 = 2^(2^0)
  • 第1次循环后：i = 2² = 2^(2^1)
  • 第2次循环后：i = (2²)² = 2^(2²) = 2^(2^2)
  • 第3次循环后：i = (2^(2²))² = 2^(2^3)
  • ...
  • 第k次循环后：i = 2^(2^k)

• 循环停止条件是i >= n，代入上面的规律得到不等式：

  2⁽²k) >= n

• 对不等式两边取以2为底的对数，简化后得到：

  2^k >= log₂n

• 再对两边取一次以2为底的对数，最终得到：

  k >= log₂(log₂n)

这说明循环最多执行log₂(log₂n)次，而每次循环内的操作是O(1)，所以整个代码的时间复杂度是O(log log n)——确实比i=2*i的O(log n)迭代次数少很多，因为平方增长的速度远快于线性乘法。

内容的提问来源于stack exchange，提问作者Shakshouk