如何求解给定嵌套循环算法的时间复杂度T(n)？

先明确代码每行的执行次数：

k = 1                # 执行1次
while (k <= n):      # 执行n+1次（k从1到n时判断成立，共n次；k=n+1时判断不成立，1次）
    j = 1            # 执行n次（外层循环每轮执行1次）
    while (j <= n):    # 每轮外层循环中执行⌊log₂n⌋+2次，总次数n*(⌊log₂n⌋+2)
        j *= 2       # 每轮外层循环中执行⌊log₂n⌋+1次，总次数n*(⌊log₂n⌋+1)
    k += 1           # 执行n次

总执行次数计算 #

把所有行的执行次数相加并化简：

T(n) = 1 + (n+1) + n + n*(⌊log₂n⌋+2) + n*(⌊log₂n⌋+1) + n
T(n) = 2n⌊log₂n⌋ + 6n + 2

对疑问的解答 #

你给出的两个选项都不正确：

• 选项T(n) = 3n +2log₂n + 3错误：只计算了一次内层循环的对数操作次数，但内层循环嵌套在外层循环中，每轮外层都要执行一次内层循环，对数项需要乘以n。
• 选项T(n) = 3n + 2n² + 3错误：误将内层循环当成O(n)的线性循环，但内层循环中j是每次翻倍（j *= 2），而非逐次加1，内层循环的时间复杂度是O(logn)，不是O(n)。

渐近时间复杂度 #

忽略低阶项和常数系数，该算法的渐近时间复杂度为O(nlogn)，即线性对数级。

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