嵌套for循环代码片段的Big-O复杂度计算求助

先厘清你之前的误区示例 #

先看这段代码：

for i in range(n): 
    for j in range(i): 
        do_something() # 该函数时间复杂度为O(1)

你之前误以为复杂度是O(n³)，问题出在错误地将两层循环的复杂度直接相乘。正确的计算逻辑是累加每一轮外层循环对应的内层执行次数：

• 当i=0时，内层循环跑0次
• 当i=1时，内层循环跑1次
• ...
• 当i=n-1时，内层循环跑n-1次

总执行次数是0+1+2+...+(n-1)，用高斯求和公式算出来是n(n-1)/2，这个式子的最高次项是n²，所以时间复杂度是O(n²)。你之前的错误在于，把外层的O(n)和内层的“单次平均O(n)”相乘得到O(n³)，但实际上内层循环的总次数本身就是O(n²)——因为外层每一次迭代的内层次数已经被累加进总和里了，不需要再重复乘外层的次数。

计算当前代码的时间复杂度 #

再看你要分析的这段代码：

for i in range(n): 
    for j in range(n**2):  # 注意：Python中`^`是按位异或，平方应该用`**`，这里按平方逻辑分析
        for k in range(i*j): 
            do_something() # 该函数时间复杂度为O(1)

计算时间复杂度的核心是累加所有do_something()的执行次数，我们可以拆成三步推导：

1. 外层循环i从0到n-1，共n次迭代；中层循环j从0到n²-1，共n²次迭代
2. 对每一组(i,j)，内层循环执行ij次，所以总次数是所有i和j组合下ij的总和，写成数学求和式就是：
   $$\sum_{i=0}^{n-1} \sum_{j=0}^{n2-1} i*j$$
3. 分步计算这个求和式：
   • 先算内层对j的求和：$\sum_{j=0}^{n2-1} i*j = i \times \sum_{j=0}^{n2-1} j$，而$\sum_{j=0}^{m-1}j = m(m-1)/2$，这里m=n²，所以近似为$i \times \frac{n^4}{2}$（忽略低次项）
   • 再算外层对i的求和：$\sum_{i=0}^{n-1} i \times \frac{n^4}{2} = \frac{n^4}{2} \times \sum_{i=0}^{{n-1}i$，$\sum_{i=0}}{n-1}i$近似为$\frac{n^2}{2}$
   • 把两者相乘得到总次数约为$\frac{n^4}{2} \times \frac{n^2}{2} = \frac{n^6}{4}$，最高次项是n⁶，所以时间复杂度是O(n⁶)

你之前算出O(n⁹)的错误原因是：错误地把内层循环的最大值（ij的最大值约为n³）代入高斯求和得到$\frac{n⁶⁺ⁿ3}{2}$后，又多乘了外层的nn²——这属于重复计算，因为求和式已经把所有i和j的组合都涵盖了，不需要再额外乘外层循环的次数。

内容的提问来源于stack exchange，提问作者Justin Höbel