如何推导该三重嵌套循环算法的大O时间复杂度？

先把目标算法贴出来：

for i ← 1 to n by 1 do
    for j ← 1 to i by 1 do
        for k ← 1 to j by 1 do
           x = x + 1
        end
    end
end

下面一步步推导时间复杂度：

1. 拆解最内层循环（k循环） #

当j的值固定时，k从1遍历到j，每轮j对应的k循环会执行j次x = x + 1操作——这是最基础的计数单元。

2. 计算中间层循环的总操作数（j循环） #

当i固定时，j从1遍历到i。我们需要把每个j对应的k循环次数加起来，也就是求1到i的整数和：
$$\sum_{j=1}^i j = \frac{i(i+1)}{2}$$
这个结果就是每轮i对应的j循环总共触发的操作次数。

3. 计算最外层循环的总操作数（i循环） #

i从1遍历到n，把每轮i对应的操作次数累加，也就是计算这个求和式：
$$\sum_{i=1}^n \frac{i(i+1)}{2}$$
展开后拆分两个独立的求和项：
$$\frac{1}{2} \left( \sum_{i=1}^n i^2 + \sum_{i=1}^n i \right)$$
代入数学上的已知求和公式：

• 1到n的整数和：$\sum_{i=1}^n i = \frac{n(n+1)}{2}$
• 1到n的平方和：$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

把这两个公式代入后化简，最终得到总操作次数为：
$$\frac{n(n+1)(n+2)}{6}$$

4. 确定时间复杂度 #

当n足够大时，低次项和常数项对结果的影响可以忽略不计，总操作次数的最高次项是$\frac{n^3}{6}$。根据时间复杂度的大O表示法，我们只保留最高次项并去掉常数系数，因此该算法的时间复杂度为O(n³)。

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