平方迭代循环的时间复杂度是否为O(log(log n))

给出的迭代循环代码如下：

for (int i = 2; i <=n; i = pow(i,2)) // 循环内操作时间复杂度为O(1)

结论 #

题目中给出的时间复杂度为*O(log(log n))*的结论完全正确。

推导过程 #

• 首先梳理迭代规律：设循环总共执行了k次，第t次（t从0开始计数）执行循环体时，变量i的取值为2^(2^t)，和你提到的迭代序列2、4、16、256……完全匹配。
• 循环的终止条件是i > n，也就是说最后一次能正常执行循环体时，i满足不等式：
  2^(2^k) ≤ n
• 对上述不等式连续做两次以2为底的对数运算：
  1. 第一次取对数后得到：2^k ≤ log₂n
  2. 第二次取对数后得到：k ≤ log₂(log₂n)
• 大O表示法中会忽略对数的底数差异、低阶项和常数项，因此循环的执行次数量级就是O(log(log n))，配合循环内O(1)的操作耗时，整体时间复杂度和结论完全一致。

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