为什么下述算法的运行时间复杂度为log(log(n))？

时间复杂度推导 #

你给出的算法代码如下：

s = 1
while s <= (log n)**2:
    s = 3 * s

推导步骤如下：

• 首先明确：循环的执行次数就是变量s从初始值1增长到超过(log n)²所需的迭代次数
• 每次迭代s都会变为原来的3倍，因此第k次迭代结束后，s的取值为3ᵏ
• 循环终止的临界条件是3ᵏ > (log n)²，我们需要求满足循环执行的最大k值，对不等式两边同时取对数可得：

  k * log(3) ≤ 2 * log(log n)
  k ≤ (2 / log(3)) * log(log n)
  

• 时间复杂度计算会忽略常数系数，因此最终的时间复杂度为O(log(log n))

如果对两层对数的量级没有概念，可以举个直观的例子：假设n = 2^(2^20)，那么log n = 2^20 = 1048576，(log n)² ≈ 10^12，此时对应的k值仅为log3(10^12) ≈ 25，迭代次数极低，完全符合log(log n)的增长特性。

内容的提问来源于stack exchange，提问作者Lalelu