为何该函数的时间复杂度为O(n³)而非O(n⁴)？

先看你给出的代码：

int sum = 0;
for (int i = n; i >= 0; i--) {
    if (i > n - 6) {
        for (int j= 0; j< n*n*n; j++) { sum -= j; }
    }
}

核心问题出在外层循环中执行内层循环的次数是固定常数，而非和n成正比：

• 外层循环虽然从i=n跑到i=0，总共n+1次迭代，但只有当i > n-6时才会触发内层循环。
• 满足i > n-6的i值只有n、n-1、n-2、n-3、n-4、n-5，一共固定6次（哪怕n小于6，满足条件的次数也是固定的小常数，不会随n增长）。
• 内层循环每次执行n³次，总执行次数就是6 * n³。根据大O表示法的规则，常数系数可以忽略，所以最终时间复杂度是O(n³)，而不是你以为的O(n⁴)——毕竟外层循环里真正触发内层的次数和n无关，不会带来额外的n倍复杂度。

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