递归式复杂度：四种方法怎么选

先判断递推式形态

面对递推式，最容易犯的错是还没看清结构就开始套公式。先观察三个问题：有几个递归项、子问题规模是否相同、非递归工作量是什么。

递推式特征	优先方法
一个递归项，规模规律缩小	递归展开
多个同规模子问题	主定理或递归树
多个不同规模子问题	递归树或代入证明
每次只减少 1	直接展开为求和式

例如 T(n)=2T(n/2)+n 符合主定理；而 T(n)=T(n/2)+T(n/4)+n² 的子问题规模不同，不能硬套。

四种方法的分工

• 猜测法给出一个可能的渐近界，再用数学归纳法验证。猜测本身不是证明。
• 递归展开把递归项逐层替换，最终得到求和式，适合结构简单的递推式。
• 递归树逐层统计总工作量，适用范围最广，也最容易看出由顶层、每一层还是叶子主导。
• 主定理是同规模分治递推式的快速结论，但前提是形如 aT(n/b)+f(n)。

可以把它们记成一句话：递归树负责发现规律，猜测法提出命题，代入完成证明，主定理负责快速判断。

递归树的核心

对 T(n)=aT(n/b)+f(n)，第 i 层有 a^i 个节点，每个节点的工作量是 f(n/b^i)。因此第 i 层总代价为：

W_i = a^i × f(n / b^i)

如果 f(n)=n^k，相邻两层总代价的比值就是 a/b^k：

• 小于 1：越往下越轻，顶层主导。
• 等于 1：每层同样重，多出一个 log n。
• 大于 1：越往下越重，叶子层主导。

通常只需写出前三层就能认出公比，无需真的把整棵树画完。最后别忘了单独检查叶子层。

主定理与空隙

主定理比较的是 f(n) 与 n^(log_b a)：后者可以理解为叶子层的工作量。

比较结果	复杂度由谁决定
f(n) 多项式级更小	叶子层
两者同阶	每一层，结果多一个 log n
f(n) 多项式级更大且满足正则条件	顶层

当差距只有 log n 或 1/log n，或者子问题规模不同，经典主定理就不适用。此时回到递归树或更一般的定理会更可靠。

解题检查表

1. 写清递归项数量、缩小比例和额外工作量。
2. 确认是否满足主定理的标准形式。
3. 使用递归树时写出节点数、单节点代价和每层总代价。
4. 判断层级代价是递增、相等还是递减。
5. 单独计算叶子数量，避免漏掉真正的主导项。
6. 最后给出上下界一致的 Θ 结论，而不只是 O。