求循环变量按前值平方递增的算法的时间复杂度（以n为基准）

首先把你给出的代码整理成更易读的格式：

#include<iostream>
using namespace std;

int main(){
    int i=2;
    while(i<=n){
        cout<<"Something"<<endl;
        i=(i*i);
    }
    return 0;
}

接下来我们一步步拆解循环的执行次数：

• 初始时i=2，第一次进入循环后，i变为2²=4
• 第二次进入循环后，i变为4²=16=2^(2²)
• 第三次进入循环后，i变为16²=256=2^(2³)
• 以此类推，第k次循环执行后，i的值是2^(2^k)

循环停止的条件是i > n，也就是说我们要找最大的k，使得第k次循环开始前的i值 ≤n。换而言之，就是满足2^(2^(k-1)) ≤ n的最大整数k。

现在通过对数变换推导这个k的量级：

1. 对不等式两边取以2为底的对数，得到2^(k-1) ≤ log₂n
2. 再对两边取一次以2为底的对数，得到k-1 ≤ log₂(log₂n)
3. 整理后可得k ≤ log₂(log₂n) + 1

这意味着循环执行的次数k和log(log n)是同量级的，所以这个算法的时间复杂度是O(log log n)（复杂度分析里对数的底数不影响大O表示，所以不用纠结是2还是10）。

这种双重对数复杂度增长极其缓慢——哪怕n是10^100这样的天文数字，循环也只会执行寥寥几次而已。

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