时间复杂度计算技巧

§ 201 时间复杂度计算技巧#

时间复杂度不想逐行死数代码怎么办？遇到递归根本不知道从哪里下手。

时间复杂度的本质是”随 $n$ 增长，核心操作被执行了多少次”，大 O 最终只保留最高阶，常数和低阶项都扔掉。所以分析的重点不是”有几行代码”，而是控制结构如何放大执行次数：

顺序结构：取最大。两段分别 $O(n)$ 和 $O(n^2)$ ，整体 $O(n^2)$ 。

循环结构：看循环变量如何接近边界。

循环形式	复杂度
`i++` 到 $n$	$O(n)$
`i *= 2` 到 $n$	$O(\log n)$

判对数阶的信号：每轮把规模乘以/除以一个固定常数。

嵌套循环：看内外层是否独立。独立则相乘；内层次数依赖外层则求和。

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++) {}  // 总次数 0+1+...+(n-1) = n(n-1)/2 → O(n²)

递归结构：先写递推式 $T(n) = aT(n/b) + f(n)$ ，再用递归树看每层总代价。

注意递归时间复杂度（总调用次数）和空间复杂度（最大递归深度）是两个不同的事。

口诀：顺序看最大，循环看次数，嵌套看乘积，分支看最坏，递归写递推。

遇到递归不要直接想”代码怎么跑”，而是先翻译成 $T(n)$ 的递推式，然后画两三层递归树，数清楚每层有几个节点、每个节点做多少工作，规律就出来了。

一个容易误判的例子：外层 i 翻倍（ $O(\log n)$ 次），内层跑 $i$ 次，总次数是 $1+2+4+\cdots+n \approx 2n$ ，整体是 $O(n)$ 而不是 $O(n \log n)$ ——因为内层不是每次都跑 $n$ 次。