含任意次数嵌套循环的时间复杂度分析及O(n²)合理性疑问

首先看你给出的伪代码：

i:1-n loop 
   j:N(i) loop
    stmt;
   end

   k:M(i) loop
    stmt;
   end
end

推导步骤 #

1. 计算总执行次数
   主循环执行n次，每次迭代里j循环跑N(i)次，k循环跑M(i)次。所有内层循环的总执行次数为：
   Total = Σ(N(i) + M(i)) ，其中i从1到n
   拆分为两个求和项后：Total = ΣN(i) + ΣM(i)

2. 分析渐近上界
   题目明确N(i)和M(i)的上限为n-1，也就是对任意i，都有N(i) ≤ n-1、M(i) ≤ n-1。代入求和式可得：

• ΣN(i) ≤ n*(n-1) = O(n²)
• ΣM(i) ≤ n*(n-1) = O(n²)

根据大O表示法的性质，两个O(n²)相加的结果仍然是O(n²)，因此总执行次数的渐近上界为O(n²)。

关于“是否可以称其为O(n²)”的结论 #

根据大O表示法的定义（描述算法运行时间的上界），称这段代码的时间复杂度为O(n²)是正确的。但要注意：这不是唯一的正确表述——如果实际的ΣN(i)+ΣM(i)增长速度更慢（比如所有N(i)、M(i)都是常数），那么O(n)也是正确的上界。只有当求和式的增长速度恰好与n²同阶时，O(n²)才是最紧的上界（此时用Θ(n²)描述更准确）。

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