执行次数为1+2+…+n的算法时间复杂度为何是O(n²)？

你提到的总执行次数为1+2+…+n的算法，时间复杂度确实是O(n²)，这个判定和“执行量级高于O(logn)”没有任何关系，是严格遵循大O表示法规则推导出来的。

示例代码 #

你给出的JavaScript实现如下：

function(n) {
    let sum = 0;

    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i+1; j++) {
            sum += 1;
        }
    }

    return sum;
}

执行次数统计 #

你统计的不同输入对应的返回值（即内层累加操作的总执行次数）如下：

核心判定逻辑 #

先明确大O表示法的基本规则：它用来描述输入规模n趋向无穷大时，算法执行步数的渐近增长上界，计算时只需要两步：

• 第一步：展开总执行次数的表达式，扔掉所有低阶项——当n足够大时，低阶项对增长速度的影响可以忽略
• 第二步：去掉剩余最高阶项前面的常数系数——常数倍的缩放不会改变增长量级

回到这段代码，外层循环i从0迭代到n-1，对应内层循环的迭代次数分别是1、2、3……n次，总次数就是等差数列求和：
总执行次数 = 1+2+3+…+n = n*(n+1)/2 = 0.5n² + 0.5n
按照规则，先扔掉低阶项0.5n，剩下最高阶项0.5n²，再去掉常数系数0.5，最终得到的最高阶就是n²，因此时间复杂度为O(n²)。

几个常见认知偏差纠正 #

• 不要把“绝对步数更少”和“复杂度更低”混为一谈
  你觉得这个算法“比O(n²)快”，本质是拿它和内外层都跑满n次的双层循环（总步数n²）比固定n下的绝对执行次数，但两者的增长量级完全一致：n翻10倍，两者执行次数都涨约100倍；n翻100倍，执行次数都涨约10000倍，这就是标准的二次方增长特征，和O(n)的线性增长、O(logn)的极慢增长有本质区别。
• 你提到的三层嵌套算法复杂度不是O(n²)
  总执行次数为1+(1+2)+(1+2+3)+…+(1+2+…+n)的三层循环，总步数展开后是n(n+1)(n+2)/6，最高阶是n³/6，对应的时间复杂度是O(n³)，属于三次方量级，比当前讨论的双层循环高一个量级。
• 复杂度判定不存在“凑档位”的规则
  从来没有“比O(logn)高就归为O(n²)”这种拍脑袋的判定逻辑，所有常见复杂度都是严格对应执行次数的最高阶：最高阶是常数就是O(1)，是logn就是O(logn)，是n就是O(n)，是nlogn就是O(nlogn)，是n²就是O(n²)，档位和阶是严格一一对应的。

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