算法设计与分析：依赖型嵌套循环O(n³)时间复杂度推导问询

云上老周

2026-7-1

三重循环时间复杂度推导（O(n³)）

先明确核心代码逻辑

从你提供的截图还原核心代码结构如下：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        for (int k = 1; k <= j; k++) {
            // 执行O(1)的基础操作（如赋值、简单运算）
        }
    }
}

逐层拆解复杂度

1. 最内层循环分析

最内层循环的循环变量是k，终止条件为k <= j——对于固定的j值，这个循环会完整执行j次，每次操作都是O(1)，因此最内层的时间开销为O(j)。

你提到的“最内层时间复杂度依赖于k而非i”，本质是k的循环次数由j决定，而j又由外层的i决定，最终还是会关联到n的量级。

2. 中间层循环分析

中间层循环的变量是j，范围是1 <= j <= i，所以中间层的总开销是把每个j对应的最内层开销累加：
$$\sum_{j=1}^{i} j = \frac{i(i+1)}{2}$$
这个求和结果的最高次项是i²，因此中间层的时间复杂度为O(i²)。

3. 最外层循环分析

最外层循环变量是i，范围是1 <= i <= n，总开销是把每个i对应的中间层开销累加：
$$\sum_{i=1}^{n} \frac{i(i+1)}{2} = \frac{1}{2}\sum_{i=1}^{n}(i² + i) = \frac{1}{2}\left( \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \right)$$
展开后最高次项为n³，根据时间复杂度的规则，忽略低次项和常数系数，最终整体时间复杂度为O(n³)。