三重循环的时间复杂度分析：O(n^3) 详解

三重循环的时间复杂度分析：O(n^3)

以下程序段的时间复杂度为 O(n^3)：

for i in range(1, n + 1):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            x = x + 1

分析过程：

• 外层循环: 循环 n 次。
• 中层循环: 循环 i 次，i 的取值范围为 1 到 n，因此平均循环 n/2 次。
• 内层循环: 循环 j 次，j 的取值范围为 1 到 i，因此平均循环 i/2 次。

因此，总的循环次数约为：

n * (n/2) * (n/2) = n^3 / 4

由于常数项对时间复杂度影响较小，所以该程序段的时间复杂度为 O(n^3)。

总结：

当嵌套循环的次数和循环次数的计算方式与变量 n 相关时，其时间复杂度通常可以由循环次数的乘积来表示。在本例中，三个循环的次数分别与 n, i 和 j 相关，因此时间复杂度为 O(n * i * j)，即 O(n^3)。