主定理

概述

主定理 为形如 $T(n)=aT(n/b)+f(n)$ 的分治递归关系式提供了三种情形的封闭解，是算法分析中最核心的工具之一。

定义

主定理（Master Theorem）

设 $a\ge 1$，$b>1$ 为常数，$f(n)$ 为渐近正函数。令 $n_0=b^{{\log }_{b}n}$，则递归关系式 $T(n)=aT(n/b)+f(n)$ 的解由以下三种情形决定。令 $c={\log }_{b}a$。

情形1：若 $f(n)=O(n^{c-\epsilon })$，其中 $\epsilon >0$，则 $T(n)=\Theta (n^c)$。

情形2：若 $f(n)=\Theta (n^c{\lg }^{k}n)$，其中 $k\ge 0$，则 $T(n)=\Theta (n^c{\lg }^{k+1}n)$。

情形3：若 $f(n)=\Omega (n^{c+\epsilon })$，其中 $\epsilon >0$，且 $f(n)$ 满足正则性条件 $af(n/b)\le \delta f(n)$（$\delta <1$），则 $T(n)=\Theta (f(n))$。

核心性质

• 情形1（递归代价主导）：叶节点层的工作量最大，$f(n)$ 增长显著慢于 $n^c$
• 情形2（平衡）：各层工作量相当，$f(n)$ 与 $n^c$ 同阶，额外产生 $\lg n$ 因子
• 情形3（根代价主导）：根节点的工作量最大，$f(n)$ 增长显著快于 $n^c$
• 正则性条件：情形3要求 $f(n)$ 在递归缩小时以常数因子衰减，排除 $f(n)$ 增长过快的不规则情况
• 不适用情形：当 $f(n)$ 与 $n^c$ 的差距不足一个多项式因子时（如 $f(n)=n^c/\lg n$），主定理无法直接应用

章节扩展

第4章：主定理统一了4.1 矩阵乘法、4.2 Strassen算法等分治算法的递归分析。4.6 连续主定理的证明用连续函数理论给出严格证明，4.7 Akra-Bazzi递归将其推广到更一般的递归形式。

参见

• 4.5 主定理 — 主定理的详细阐述与实例
• 4.6 连续主定理的证明 — 严格数学证明
• 4.7 Akra-Bazzi递归 — 推广形式
• 代入法 — 主定理无法适用时的替代方法
• 4.4 递归树法 — 理解主定理的直觉工具