关于函数‘loops’的时间复杂度疑问：为何是O(n³)而非O(n²)

嘿，你的分析思路其实已经对了一半，但确实漏掉了关键的一环——while循环内部的操作复杂度！

首先明确：如果这个函数的时间复杂度是O(n³)，那大概率是你只计算了外层循环与while循环的总迭代次数，但没考虑到每一次while循环的执行，都伴随着另一个O(n)级别的操作。

举个最常见的对应场景，假设loops函数的结构是这样的：

def loops(n):
    for i in range(1, n+1):
        j = i
        while j <= n:
            # 这里有一个内层循环，每次执行n次操作
            for k in range(n):
                do_something()  # 假设这是O(1)的基础操作
            j += 1

我们来拆解计算总操作次数：

• 外层for循环：i从1到n，共n次迭代。
• 对应每个i，while循环的执行次数是n - i + 1次（比如i=1时执行n次，i=2时执行n-1次…i=n时执行1次），所以while循环的总次数是1+2+...+n = n(n+1)/2，这部分和你的分析完全一致，确实是O(n²)的量级。
• 但核心问题来了：每一次while循环内部，都有一个执行n次的内层循环。所以总操作次数就是n(n+1)/2 * n = n²(n+1)/2，当n趋近于无穷大时，低阶项和常数系数可以忽略，最终时间复杂度就是O(n³)。

简单说，你之前只统计了“有多少轮while循环”，但没算“每一轮while循环要做多少事”——如果每轮都要做O(n)的工作，那总复杂度自然就从O(n²)升级到O(n³)了。

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