Master Theorem
主定理给出分治递推 T(n)=aT(n/b)+f(n) 的渐近界，分三种情况由 f 与 n^(log_b a) 比较。
用途
快速分析分治算法复杂度无需递归展开。
机制
主定理比较递归树中叶子总耗时与内部节点合并总耗时：记 c=log_b a。情况一（叶重，递归占优）：f=O(n^(c-ε)) 时 T=Θ(n^c)；情况二（同阶带对数因子）：f=Θ(n^c log^k n) 时 T=Θ(n^c log^(k+1) n)；情况三（根重，合并占优）：f=Ω(n^(c+ε)) 且满足正则条件时 T=Θ(f)。
用例
- 复杂度分析
- 分治算法
- 递推求解