如何分析嵌套循环时间复杂度

嵌套循环的时间复杂度由各层循环规模的乘积主导；当内层循环规模为 n−2、外层为 n 时，总操作数为 n(n−2) = n²−2n，按大 O 记号规则，最高次项 n² 决定其时间复杂度为 O(n²)。

在算法分析中，时间复杂度的核心目标是刻画输入规模 n 增大时，运行时间的增长趋势，而非精确计数。我们以如下典型嵌套结构为例：

for i in range(0, n):        # 执行 n 次
    for j in range(0, n - 2): # 每次执行 (n - 2) 次
        # 常数时间操作（如赋值、比较、算术运算）

外层循环迭代 n 次，内层循环每次迭代 n − 2 次，因此总执行次数为：
[ T(n) = n \times (n - 2) = n^2 - 2n ]

根据大 O 符号的定义：

若存在正常数 (c) 和 (n_0)，使得对所有 (n \geq n_0)，有 (0 \leq T(n) \leq c \cdot n^2)，则 (T(n) = O(n^2))。

显然，当 (n \geq 2) 时，(n^2 - 2n \leq n^2)，故取 (c = 1, n_0 = 2) 即满足条件。更进一步，由于 (-2n) 是低阶项，在渐近分析中可被忽略；而常数因子（如系数 1）和低阶项均不改变主导增长速率——因此 O(n² − 2n) ≡ O(n²)。

✅ 关键原则总结：

• 只保留最高次幂项（主导项）；
• 忽略所有常数系数（如 5n² → n²）；
• 忽略所有低阶项（如 n² + 100n + 42 → n²）；
• 对多项式表达式，时间复杂度即为其首项的阶数。

⚠️ 注意事项：

• 此结论成立的前提是 n − 2 与 n 属于同一数量级（即 (\lim_{n \to \infty} \frac{n-2}{n} = 1)），若内层改为 range(0, sqrt(n)) 或 range(0, log n)，结果将变为 (O(n\sqrt{n})) 或 (O(n \log n))，不可一概而论；
• 实际性能可能受缓存、分支预测等硬件因素影响，但时间复杂度描述的是理论渐近上界，与具体运行环境无关；
• 当 n 很小时（如 n < 5），低阶项或常数开销可能显著，此时大 O 分析不反映实际耗时，需结合基准测试综合评估。

综上，只要内外层循环的迭代次数均为 n 的线性函数（如 an + b, cn + d，其中 a,c > 0），其嵌套结构的时间复杂度恒为 O(n²)。理解这一简化逻辑，是准确分析更复杂嵌套（如三重循环、非均匀边界）的基础。