Complexity/big 乘法增量为 i 的循环的 theta
Complexity/big theta of loop with multiplicative increment of i
我正在尝试找出以下的时间复杂度/大 theta：
def f(n):
i = 2
while i <n:
print(i)
i = i*i
我知道如何解决这个问题的唯一方法是找到 i_k 的通用公式，然后求解 i_k >= n 的方程式，但是我最终得到了一个日志(logn/log2)/log(2) 方程作为我的 k 值，这对我来说似乎是非常错误的，我不确定如何将其转换为大的 theta 表达式。如有任何帮助，我们将不胜感激！
这个答案看起来不错，真的！如果将log x / log 2改写为log2 x（或简称lg x），则迭代次数为lg lg n。由于在循环的第k次迭代中i的值为22k，这意味着当i达到值2[=时循环停止15=]2lg lg n = 2lg n = n，匹配循环边界。
更一般地说，一个值在超过 n 之前可以平方的次数是 Θ(log log n)，类似地，在将数字 n 降为常数之前可以取平方根的次数是Θ(log log n)，所以你的答案几乎就是你所期望的。
我正在尝试找出以下的时间复杂度/大 theta：
def f(n):
i = 2
while i <n:
print(i)
i = i*i
我知道如何解决这个问题的唯一方法是找到 i_k 的通用公式，然后求解 i_k >= n 的方程式，但是我最终得到了一个日志(logn/log2)/log(2) 方程作为我的 k 值，这对我来说似乎是非常错误的，我不确定如何将其转换为大的 theta 表达式。如有任何帮助，我们将不胜感激！
这个答案看起来不错，真的！如果将log x / log 2改写为log2 x（或简称lg x），则迭代次数为lg lg n。由于在循环的第k次迭代中i的值为22k，这意味着当i达到值2[=时循环停止15=]2lg lg n = 2lg n = n，匹配循环边界。
更一般地说，一个值在超过 n 之前可以平方的次数是 Θ(log log n)，类似地，在将数字 n 降为常数之前可以取平方根的次数是Θ(log log n)，所以你的答案几乎就是你所期望的。