此 for 循环的时间复杂度： for (i = 2; i < N; i = i * i)?

我们现在正在学习时间复杂度，而我在这个例子中遇到了很多麻烦。

for (i = 2; i < n; i = i * i)
{
     ... do something ...
}

教授说这是 O(sqrt(N))，但我不确定我是否相信。毕竟，如果 N=16，它只运行 2 次，而不是 4 次，对吧？

我的解决方法： 2^(2k) = N，其中 k 是循环运行的次数。 除去常数因子，k 运行 log(N) 次。 我这里哪里出错了？感谢您对此事的任何建议。

你是正确的，你的老师是错误的（至少，他们的界限不严格），我喜欢你所做的分析，但我认为你在最后一步得出了错误的结论。

很高兴您一路上查看了所有中间值。你是正确的，j 所采用的值序列是 2、4、16、256 等。如果我们将其重写为 2 的幂，请注意该序列采用的值

2¹, 2², 2⁴, 2⁸, ...

More generally, after k iterations of the loop, the value of j is 2^2k (as opposed to 2^2k, as you initially wrote). This means that to determine the number of loop iterations, you want to determine when

2^2k = n.

在这里，你必须采取two对数来解决这个问题：

2^2k = n

2^k = lg n

k = lg lg n

所以循环的迭代次数为O(log log n)，低于你的老师给你的 O(√n) 和你想出的 O(log n)。

物有所值，当您重复计算一个数字的平方根时，您经常会看到 O(log log n) 的行为 https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity（你可以在一个数下降到一个常数之前对其求平方根 O(log log n) 次），所以如果你反向运行这个并继续对一个值进行平方，你会看到 O(日志日志n)出现。