2次迭代的幂运行时间

Question

例如：

for (int i = 2; i <=n; i = pow(i,2)) // O(1) time here)

log(log(n)) 从 2 4 16 256 ... 2^(2^n) 是否正确？

Answer 1

是的，这个循环的时间复杂度是O(log(log(n)))。

动机： i 增长为 ((2^2)^2)^...^2 = 2^{(2 * 2 * ... * 2)} = 2^{2^(k-1)} 其中 k 是迭代次数。因此我们必须解决：

n = 2^{2^(k-1)}

log₂(n) = 2^(k-1)

log₂(log₂(n)) = k-1

k = log₂(log₂(n)) + 1 = O(log(log( n)).▢