内层依赖外层的嵌套循环Big O notation时间复杂度计算问题

首先给出你提到的代码块：

for (int x = 0; x < n; x++)
   for (int y = 0; y < n; y++)
      for (int z = 0; z < y; z++)
         anything();

你的计算思路核心错误是重复统计了第二层循环的执行影响，具体推导逻辑如下：

• 我们逐层统计实际执行次数：
  1. 最外层x循环独立执行n次，每次执行都会触发内层y、z循环的完整逻辑
  2. 对任意固定的x值，第二层y循环会执行n次，y的取值依次为0、1、2...n-1
  3. 对任意固定的y值，第三层z循环的执行次数等于y的值：y=0时执行0次，y=1时执行1次，直到y=n-1时执行n-1次
• 对单次x循环来说，内层y+z循环的总执行次数是0+1+2+...+(n-1) = n(n-1)/2，这个求和结果已经把第二层y循环的n次执行的影响完全计算在内了，不需要再额外乘以n
• 最后乘以最外层x循环的n次执行，总执行次数为 n × n(n-1)/2 = (n³ -n²)/2，取最高阶项后时间复杂度为O(n³)

你之前得到O(n^4)的错误结果，本质是把z循环对单个y值的执行次数的求和结果，错误当成了单个y值对应的z循环执行次数，额外多乘了一次第二层y循环的执行次数n。

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