求三层嵌套for循环的时间复杂度（第三层依赖第一层）

先看你给出的代码：

for (int i = 0; i < n*n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < i; k++) {
            // print some statement here
        }
    }
}

循环拆解与次数计算 #

• 第一层循环：i从0到n²-1，总共执行n²次迭代。
• 第二层循环：每一轮i的迭代中，j都会从0到n-1，所以每轮i对应n次j循环。
• 第三层循环：每一轮j的迭代中，k的执行次数等于i（当i=0时，k循环不执行，次数为0）。

总执行次数的计算逻辑是：第二层循环的总次数 × 第三层循环在所有i下的执行次数之和，也就是：

总次数 = n × Σ（i从0到n²-1 的i）

根据等差数列求和公式，Σi从0到m-1的i = m(m-1)/2，这里m=n²，代入后可得：

Σi = n²(n² - 1)/2 ≈ n⁴/2

（当n趋近于无穷大时，-1对结果的影响可以忽略）

再乘以第二层循环的n，总执行次数约为n⁵/2，因此时间复杂度为O(n⁵)。

对你疑问的解答 #

1. 你之前推导的n(1+2+3+…)方向对，但求和上限错误：第一层循环的上限是n²，不是n，所以求和应该加到n²-1，而非n-1。
2. 第二层循环的n必须乘进去：每一轮i的迭代里，j循环执行n次，每次j循环都对应i次k循环，所以总次数是n乘以所有i的和，不能省略这个乘数。

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