07 主定理与递归树法 ★★☆☆☆ (忘发了。)

主定理（Master Theorem）用于快速求解分治递归式  的渐近复杂度，是分析归并排序、二分查找、Karatsuba 乘法等分治算法时间复杂度的核心工具，常出现在初赛复杂度分析题中。

Tips：部分内容由 AI 生成，如发现问题请在评论区留言。

一、主定理

对于形如

的递归式，其中 、、 渐近为正。令

（即  为以  为底  的对数，计算时可用 ），比较  与  的大小，分三种情形：

情形 1： 多项式地小于 ，即存在  使

则

情形 2： 与  同阶，即

则

情形 3： 多项式地大于 ，即存在  使

且满足正则条件（存在常数  与充分大的 ，使 ），则

二、判定步骤

1. 1. 确认递归式形如 ，且 、。
2. 2. 计算 （也就是看  是多少）。
3. 3. 比较  与 ，判断落入哪种情形。

三种情形背后的直观解释，见下文「递归树法」。

三、扩展主定理

当  含有  因子时，标准主定理往往套不进去——因为「只差  因子」既不算多项式地大，也不算多项式地小。此时用扩展主定理：设

其中 、 为常数，，则：

• • 若 ：

• • 若 ：

• • 若 ：进一步看  的取值
• • ：

• • ：

• • ：

例：

• • ：。
• • ：。

对照：、、（）分别就是标准主定理的情形 3、1、2。

四、递归树法

递归树法是把递归式逐层展开成一棵树，算出每层总代价再求和，是最直观也最通用的方法——主定理的三种情形本质上就是递归树求和的三类结果，主定理搞不定的式子也能用它硬算。

方法：对 ，逐层展开：

• • 第 0 层（根）：1 个节点，代价 。
• • 第 1 层： 个节点，每个 ，合计 。
• • 第 2 层： 个节点，每个 ，合计 。
• • 第  层： 个节点，每个 ，合计 。
• • 叶子层：共  个叶子，每个代价 ，合计 。

总代价（，不含叶子层）：

把这个级数求和，对应三种情形：

• • 情形 1：每层代价逐层递减，几何级数，叶子层占主导 。
• • 情形 2：每层代价相等，共  层 。
• • 情形 3：每层代价逐层递增且收敛，根层占主导 。

示例

例 1（情形 2）：。第  层代价 ，每层都是 ，共  层 。

例 2（情形 3）：。第  层代价 ，几何级数收敛 。

例 3（非标准形式）：。递归树是一条链：。主定理用不了，递归树直接求和即可。

五、常见例子

说明：二分查找的  与  同阶，落情形 2；二叉树遍历的  比  小得多，落情形 1。

六、注意事项

1. 1. 必须"多项式地"大或小：要相差 （）那么多，只差一个  因子不够。例如  与 ，既不是 （情形 2），也不是 （情形 3），此时改用扩展主定理。
2. 2. 情形 3 需验证正则条件：（）。常见的  或  一般都满足，但并非自动成立。
3. 3. 形式不符时不能用：如 （ 不满足 ）等，需改用递归树法、代入法或 Akra-Bazzi 法。

七、总结

• • 主定理求解 ，核心是比较  与 。
• • 情形 1（ 更小）；情形 2（同阶）；情形 3（ 更大且满足正则条件）。
• •  含  因子时，用扩展主定理。
• • 主定理和扩展主定理都搞不定时，用递归树法逐层求和，这是最通用的兜底方法。