algorithm - 这段代码的时间复杂度是多少loglogn？

Question

我是初学者，我很困惑这段代码的时间复杂度是 log log n。

while(i<=n)
{
i = i*i;
}

Answer 1

对于 n = k¹⁶:

iteration 1: i = k
iteration 2: i = k^2
iteration 3: i = k^4
iteration 4: i = k^16

所以基本上你可以证明你正在为 k^m 迭代 log(m) 次，其中 m = log(k)。