主定理（Master Theorem）是什么？如何用它分析分治算法的复杂度？

简化版

主定理是分析分治递归式 T(n) = a·T(n/b) + f(n)（a≥1, b>1）复杂度的公式。核心是拿 f(n) 和 n^(log_b a) 比大小：谁大谁主导。分三种情况——f(n) 小（叶子主导，结果 Θ(n^log_b a)）、一样大（每层均衡，结果 Θ(n^log_b a · log n)）、f(n) 大且满足正则条件（根主导，结果 Θ(f(n))）。有了它，归并、二分、Karatsuba 的复杂度都能一眼报出来。

详细版

递归式的形状：T(n) = a·T(n/b) + f(n)

a：每次分成几个子问题（子问题个数）；
n/b：每个子问题的规模（原来的 1/b）；
f(n)：分解 + 合并的代价。

先算一个临界值 n^(log_b a)（叫「分水岭」，代表递归树所有叶子的总代价），再和 f(n) 比：

情况	条件	结论
情况一	`f(n) = O(n^(log_b a − ε))`，某个 `ε>0`（`f` 比分水岭小一个多项式量级）	`T(n) = Θ(n^log_b a)`
情况二	`f(n) = Θ(n^(log_b a))`（一样大）	`T(n) = Θ(n^log_b a · log n)`
情况三	`f(n) = Ω(n^(log_b a + ε))`，某个 `ε>0`，且满足正则条件 `a·f(n/b) ≤ c·f(n)`（某 `c<1`）	`T(n) = Θ(f(n))`

套用示例：

归并排序 T(n)=2T(n/2)+O(n)：a=2,b=2，n^(log₂2)=n，f(n)=n → 情况二 → Θ(n log n)。
二分查找 T(n)=T(n/2)+O(1)：a=1,b=2，n^(log₂1)=n^0=1，f(n)=O(1) → 情况二 → Θ(log n)。
Karatsuba 大数乘法 T(n)=3T(n/2)+O(n)：n^(log₂3)≈n^1.585，f(n)=n 更小 → 情况一 → Θ(n^1.585)。
二叉树遍历 T(n)=2T(n/2)+O(1)：n^(log₂2)=n，f(n)=O(1) 更小 → 情况一 → Θ(n)。

完整版教学

一、主定理解决什么问题：一眼看穿分治复杂度

分治算法的运行时间几乎都能写成递归式 T(n) = a·T(n/b) + f(n)。手动展开递归、画递归树求和很费劲，主定理把这类最常见的递归式的答案直接背成公式：给定 a、b、f(n)，套一下就得出复杂度。它是分析分治效率最趁手的工具。

先明确三个量的含义：

a = 每层把一个问题分裂成几个子问题；
b = 每个子问题规模缩小的倍数（变成 n/b）；
f(n) = 在当前这一层，「分」和「合并」花的时间。

二、关键是那条「分水岭」：n^(log_b a)

主定理的一切都围绕比较两个量：f(n) 和 n^(log_b a)。这个 n^(log_b a) 从哪来？

递归树一共有 log_b n 层。第 k 层有 a^k 个子问题。递归到底（叶子）时子问题规模为 1，叶子的数量是 a^(log_b n) = n^(log_b a)。所以 n^(log_b a) 代表「所有叶子的总代价」，也就是「不断分裂产生的子问题总数」这一侧的开销。

而 f(n) 代表「每往下分一层、合并时」这一侧的开销。主定理的本质就是问：

是「顶部一层层合并的代价 f(n)」大，还是「底部海量叶子的代价 n^(log_b a)」大？谁大，总复杂度就由谁主导。

三、三种情况的直觉：递归树的哪一层在主导

把递归树每一层的代价加起来，会呈现三种形态：

情况一（叶子主导）：f(n) 比分水岭 n^(log_b a) 小一个多项式量级。往下每层代价越来越大，最底层的叶子总代价最大，主导结果 → T(n)=Θ(n^log_b a)。
情况二（各层均衡）：f(n) 和分水岭同量级。每一层代价差不多相等，一共 log n 层，于是总代价 = 每层代价 × 层数 → T(n)=Θ(n^log_b a · log n)。归并排序就是这种。
情况三（根部主导）：f(n) 比分水岭大一个多项式量级，且满足正则条件。往下每层代价越来越小，最顶层（根）的 f(n) 最大，主导结果 → T(n)=Θ(f(n))。

情况三额外要求的正则条件 a·f(n/b) ≤ c·f(n)（c<1）意思是「子问题合并代价之和，比父问题合并代价明显小」，保证代价确实是往上越来越大、由根主导。对绝大多数多项式型的 f(n)，这个条件自动成立。

四、四个示例，把三种情况都走一遍

归并排序：T(n)=2T(n/2)+O(n)。a=2,b=2 → n^(log₂2)=n^1=n。f(n)=n，和分水岭 n 一样大 → 情况二 → Θ(n log n)。这也是「为什么归并稳定地是 n log n」的严格来源。

二分查找：T(n)=T(n/2)+O(1)。a=1,b=2 → n^(log₂1)=n^0=1。f(n)=O(1)，和分水岭 1 一样大 → 情况二 → Θ(1·log n)=Θ(log n)。

Karatsuba 大整数乘法：T(n)=3T(n/2)+O(n)。a=3,b=2 → n^(log₂3)≈n^1.585。f(n)=n，比 n^1.585 小 → 情况一 → Θ(n^1.585)，比朴素的 O(n²) 快。

Strassen 矩阵乘法：T(n)=7T(n/2)+O(n²)。a=7,b=2 → n^(log₂7)≈n^2.807。f(n)=n²，比 n^2.807 小 → 情况一 → Θ(n^2.807)，比朴素矩阵乘法 O(n³) 快。

五、主定理用不了的边界情况

主定理不是万能的，下面几种情况套不上：

f(n) 和分水岭差距不是「多项式量级」。 比如 T(n)=2T(n/2)+n log n，f(n)=n log n 比分水岭 n 大，但只大了个 log n（不是大一个 n^ε），落在情况二和三之间的「缝隙」里，主定理失效。此题真实答案是 Θ(n log² n)，要用递归树或推广的主定理求。
a 不是常数、或子问题规模不是 n/b 的均匀形式（如 T(n)=T(n/3)+T(2n/3)+n），标准主定理不适用，改用递归树法或 Akra–Bazzi 定理。
b≤1 或 a<1：不符合前提。

遇到套不上主定理的，退回画递归树逐层求和总能算，只是麻烦些。

六、递归式、合并证明与数字推演

这道题的分治闭环是：递归树第 i 层有 a^i 个规模 n/b^i 的子问题，需比较叶子规模 n^(log_b a) 与每层非递归代价。递归调用只保证子问题正确，原问题能否正确仍取决于合并步骤是否覆盖所有情况且不重不漏。

T(n)=aT(n/b)+f(n)
临界量 g(n)=n^(log_b a)
递归树核对：每层子问题数 × 单个子问题的非递归代价

带数字推演：归并 a=2,b=2,f=n，g=n，属于第二类得到 Θ(n log n)；二分 a=1,b=2,f=1 得 Θ(log n)。推演时应记录每层输入规模、进入哪些子问题、合并新增了什么信息，不能只写最终答案。

记忆钩子：先写“分成什么、递归返回什么、怎样合并”，再列递推式；只会套主定理而说不清合并，说明算法还没有真正掌握。

七、实现代价、退化条件与替代方案

实现边界是：a≥1、b>1；不等规模、参数随 n 变化或正则条件不满足时不能生搬主定理。除了渐进时间，还要把递归栈、辅助数组、输入是否被修改以及最坏输入考虑进去。

检查项	面试中要回答的内容
基本情况	规模 0 或 1 时如何直接返回
规模缩小	每次递归是否严格靠近基本情况
合并正确性	子解怎样推出原问题答案
资源代价	递归深度、辅助结构与数据复制
退化保护	随机化、阈值切换、预排序或迭代改写

测试至少覆盖最小规模、奇偶长度、全部相等、严格有序/逆序、极端偏斜划分和会触发最大计数或溢出的数据。若存在更直接的线性算法、堆算法或动态规划，还要说明分治方案的教学价值与工程取舍。

八、常见误区与追问

误区：只比较 f(n) 和 n。 应比较 f(n) 与 n^(log_b a)。
误区：三种情况都不需要附加条件。 第三类通常需要正则条件 a f(n/b)≤c f(n)。
误区：T(n)=T(n-1)+n 可用主定理。 子问题不是 n/b 形式。
追问：临界量表示什么？ 它对应递归树叶子数量/总代价的自然尺度。
追问：第二类为什么多一个 log n？ 各层代价同阶，共有 Θ(log n) 层。
追问：遇到不规则递推怎么办？ 画递归树、代入证明或使用 Akra–Bazzi 等工具。

九、加强记忆

主定理分析 T(n)=aT(n/b)+f(n)：先算分水岭 n^(log_b a)（= 叶子总代价），再和 f(n) 比。f 小 → 叶子主导 Θ(n^log_b a)（情况一）；一样大 → 每层均衡 Θ(n^log_b a·log n)（情况二）；f 大且满足正则条件 → 根主导 Θ(f(n))（情况三）。归并是情况二得 n log n，二分是情况二得 log n，Karatsuba/Strassen 是情况一。差距不到多项式量级（如 +n log n）时主定理失效，改用递归树或 Akra–Bazzi。

简化版

详细版