嵌套for循环时间复杂度一定为O(n²)吗？附代码求分析

结论非常明确：不一定。嵌套循环的时间复杂度从来不是由嵌套层数直接决定的，核心判断依据是所有循环内O(1)操作的总执行次数的渐近量级，两层循环可能得到O(n)、O(nlogn)、O(n²)等不同结果，不存在固定的复杂度结论。

给出的代码片段如下：

for (i = 1; i <= n; i++)
{
   for (j = n; j >= i; j--)
   // 分析前提：默认循环体为O(1)时间的基础操作，无break/return等提前跳出逻辑
}

在线工具给出的O(n)结果是错误的，我们可以通过逐次统计循环执行次数计算总操作量：

• 外层i=1时，内层j从n递减到1，共执行n次
• 外层i=2时，内层j从n递减到2，共执行n-1次
• 外层i=3时，内层j从n递减到3，共执行n-2次
• ...
• 外层i=n时，内层j仅取j=n这1个值，共执行1次

总执行次数是首项为1、末项为n的等差数列求和：
总次数 = 1 + 2 + 3 + ... + (n-1) + n = n*(n+1)/2
对该结果做渐近复杂度化简，忽略常数系数、低次项后，这段代码的时间复杂度为O(n²)。

补充说明：两层嵌套循环出现O(n)复杂度是完全可能的，典型场景是内层循环的执行次数是和n无关的固定常数，或者两层循环的控制变量强绑定、内层总执行次数累加为线性量级，例如下方代码就是典型的两层嵌套但复杂度为O(n)的情况：

// 两层嵌套，时间复杂度O(n)
for (i = 1; i <= n; i++) {
    for (j = 1; j <= 2; j++) { // 内层每次固定执行2次，和n的规模无关
        // O(1)操作
    }
}

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