我认为这是log（logn），因为周期重复log（logn）次...
j=1;
i=2;
while (i <= n) do {
B[j] = A[i];
j = j + 1;
i = i * i;
}
您是对的，O(lg(lg n))在这里lg代表以2为底的对数。
原因是的值序列i受该规则约束i = prev(i) * prev(i)，对于步骤1、2、3、4，...，结果为2、2 ^ 2、2 ^ 4、2 ^ 8，...。换句话说，迭代i后的k值为2^{2^k}。
因此，循环将在2^{2^k} > n或停止k > lg(lg(n))（只要lg对不等式的两端进行两次。不等式仍然有效，因为它lg是一个递增的函数。）
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句