algorithm - 具有 i 的乘法增量的循环的复杂性/大 theta

Question

我试图找到以下的时间复杂度/大 theta:

def f(n):
    i = 2
    while i <n:
        print(i)
        i = i*i

我知道如何解决这个问题的唯一方法是找到 i_k 的通用公式，然后求解 i_k >= n 的方程，但是我最终得到了 log(logn/log2)/log(2)方程作为我的 k 值，这对我来说似乎是非常错误的，我不确定如何将其转换为大的 theta 表达式。任何帮助将不胜感激!

Answer 1

实际上，这个答案看起来不错!如果将 log x/log 2 重写为 log₂ x(或简称 lg x)，则迭代次数为 lg lg n。由于在循环的第k次迭代中i的值为2^2k，这意味着当i达到值2^{2lg时循环停止lg n} = 2^{lg n} = n，匹配循环边界。

更一般地说，一个值在超过 n 之前可以平方的次数是 Θ(log log n)，类似地，在将一个数 n 降为常数之前可以求平方根的次数是 Θ( log log n)，所以你的答案几乎是你所期望的。