这个算法的时间复杂度是多少？

Question

for i = 1 to n do
    j = 2
    while j < i do
        j = j * j

我认为它的时间复杂度是：log(n!) = n * log(n)。

但解决方案说它是：n * loglog(n) 我不明白为什么？

Answer 1

在下面的解释中，我假设所有的算术和比较运算都是O(1)。

for i = 1 to n do

下面重复N次，使得n *部分在解中。

    j = 2
    while j < i do
        j = j * j

以上计算了以下序列的第一个数字，即 >= i ：

2 = 2^(2^0)
4 = 2^(2^1)
16 = 2^(2^2)
256 = 2^(2^3)
65536 = 2^(2^4)
...

所以你唯一需要做的就是找到 i 和 2^(2^i) 之间的关系。还有 log(log(2^(2^i))) = log(2^i) = i.

Answer 2

让我们分解它并从内到外工作。

想象一下：

j = 2
while j < n do
  j = j * 2

j 变为 2、4、8、16...，因此如果 n 的大小翻倍，则 j 只需要大约一次迭代就可以超过它。这基本上就是对数的定义。

你的案例中的内部循环有点不同：

j = 2
while j < n do
  j = j * j

现在 j 达到 2、4、16、256、65536...并且更容易超过 n。在第一种情况下，j 每次迭代呈指数增长，现在呈双倍指数增长。但我们感兴趣的是相反的情况——j 在 log(log(n)) 步中超过 n。

然后外循环就意味着你这样做 n 次。

What is the time complexity for this Algorithm?