algorithm - 找出算法的时间复杂度？

Question

我认为是 log(logn) 因为循环重复 log(logn) 次...

j=1;
i=2;
while (i <= n) do {
    B[j] = A[i];
    j = j + 1;
    i = i * i;
}

Answer 1

你是对的，它是 O(lg(lg n)) 其中 lg 代表以 2 为底的对数。

原因是 i 的值序列服从规则 i = prev(i) * prev(i)，结果是 2 , 2^2, 2^4, 2^8, ... 对于步骤 1, 2, 3, 4, ... 换句话说， k 之后的 i 的值 迭代是 2^{2^k}。

因此，循环将在 2^{2^k} > n 或 k > lg(lg(n)) 时停止(只需取 lg 两次到不等式的两边。不等式仍然有效，因为 lg 是递增函数。)