内层循环依赖外层的嵌套for循环时间复杂度如何计算

你给出的代码如下：

for(i = 0; i < n*n; i++)
   for(j = 0; j <= i/5; j++)
      print("Hello World!");

以下是时间复杂度的推导过程：

步骤1：确定每层循环的执行次数 #

• 外层循环：i从0开始到n²-1结束，共执行n²次（你之前认为的n²+1是错误的，循环终止条件是i < n*n，i=n²时不会进入循环体）
• 内层循环：对每个固定的i，j从0到i/5（含两端），因此单次外层循环对应的内层执行次数为 ⌊i/5⌋ + 1 次，加1是因为包含j=0的初始值。

步骤2：计算总操作次数 #

print语句的总执行次数等于所有外层循环对应的内层次数之和，公式为：

总次数 = Σ（i=0 到 i=n²-1）(⌊i/5⌋ + 1)

步骤3：化简求和得到量级 #

大O时间复杂度只关心最高阶的量级，常数系数和低阶项都可以忽略：

1. 向下取整的误差为常数级，因此⌊i/5⌋ ≈ i/5，1/5的常数系数后续可以直接忽略
2. 求和式可以近似为 (1/5) * Σ（i=0到i=n²-1）i
3. 代入等差数列求和公式：Σ（i=0到m-1）i = m(m-1)/2 ≈ m²/2，这里m等于n²，代入后得到：

   总次数 ≈ (1/5) * (n²)² / 2 = n⁴ / 10
   

4. 即使考虑向下取整的误差、最后不足5个i的剩余项，这些都属于O(n²)的低阶项，不会影响最高阶的量级。

最终结论 #

这段嵌套循环的时间复杂度为 O(n⁴)。

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