time-complexity - 这个 for 循环的时间复杂度 : for (i = 2; i < N; i = i * i)?

Question

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

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

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

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

Answer 1

你是对的，你的导师是错的(至少，他们的界限并不严格)，我喜欢你所做的分析，但我认为你在最后一步得出了错误的结论。

很高兴您在此过程中查看了所有中间值。您认为 j 取值的序列是 2、4、16、256 等是正确的。如果我们将事物重写为 2 的幂，请注意该序列取值

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

更一般地，在循环的 k 次迭代之后，j 的值为 22k(而不是您最初编写的 22k)。这意味着要确定循环迭代次数，您需要确定何时

2^2k = n.

在这里，你必须取两个对数来解决这个问题:

2^2k = n

2^k = lg n

k = lg lg n

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

物有所值， you often see O(log log n) behavior when you repeatedly take square roots of a number (你可以在一个数字下降到一个常数之前取它的平方根 O(log log n) 次)，所以如果你反向运行这个并继续平方一个你会看到 O( log log n) 出现。