特殊三层嵌套循环的时间复杂度推导正确性验证

你的推导过程存在逻辑错误，最终得到的O(n⁴)结果不正确，这段三层嵌套循环的实际时间复杂度为O(n³)。

for i:=1 to n do
    for j:=1 to i do
        for k:=1 to j do Mod A

• 核心操作Mod A的执行耗时为常数M，耗时不随循环变量取值变化。

你原来的计算逻辑是把三层循环的执行次数拆成(1+2+..+i)和(1+2+....+n)相乘，甚至在最终化简式里保留了仅在循环内部生效的局部变量i，本质是搞错了嵌套循环的计数规则：嵌套循环的总执行次数是外层每固定一个取值，内层完整跑完对应取值范围的累加结果，不是把各层循环的独立求和结果直接相乘。

从最内层循环开始逐层向外累加计数即可：

1. 最内层k循环：当外层i、j取值固定时，k从1遍历到j，一共执行j次Mod A操作
2. 中间j循环：当外层i取值固定时，j从1遍历到i，每个j值对应内层k循环执行j次，因此固定i时，内层两层的总执行次数为 1+2+…+i = i*(i+1)/2
3. 最外层i循环：i从1遍历到n，每个i值对应内层两层总执行i*(i+1)/2次，因此全流程总执行次数为i从1到n时所有i*(i+1)/2的累加和

代入基础求和公式计算总次数：
总执行次数 = 1/2 *（1到n的平方和 + 1到n的等差数列和）
其中：

• 1到n的等差数列和：n*(n+1)/2
• 1到n的平方和：n*(n+1)*(2n+1)/6
  展开化简后，表达式的最高次项为n³/6，乘以常数M后，忽略低次项和常数系数，最终时间复杂度为O(n³)。

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