主定理

概述

主定理（Master Theorem）是求解形如 $T(n)=aT(n/b)+f(n)$ 的递推关系的核心工具，其中 $a\ge 1$，$b>1$。它通过比较递归代价与合并代价的相对大小，将递推关系分为三种情形，直接给出渐近解。主定理是分析分治算法时间复杂度的首选方法。

定义

主定理（Master Theorem）

设 $a\ge 1$ 且 $b>1$ 为常数，$f(n)$ 为渐近正函数。递推关系：

$T(n)=aT(n/b)+f(n)$

令 $n_b^{{\log }_a}$（即 $n^{{\log }_{b}a}$）为递归树中叶节点的代价。则根据 $f(n)$ 与 $n^{{\log }_{b}a}$ 的比较，分三种情形：

情形一：递归代价主导

若 $f(n)=O(n^{{\log }_{b}a-\epsilon })$，其中 $\epsilon >0$，则：

$T(n)=\Theta (n^{{\log }_{b}a})$

直觉：合并代价远小于递归代价，叶节点主导总代价。

情形二：两者相当

若 $f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$，其中 $k\ge 0$，则：

$T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$

当 $k=0$ 时（最常见情况），$T(n)=\Theta (n^{{\log }_{b}a}\log n)$。

直觉：合并代价与递归代价同阶，各层代价相当，多出 $\log n$ 层。

情形三：合并代价主导

若 $f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$，其中 $\epsilon >0$，且对某个常数 $c<1$ 和足够大的 $n$，有 $af(n/b)\le cf(n)$（正则性条件），则：

$T(n)=\Theta (f(n))$

直觉：合并代价远大于递归代价，根节点主导总代价。

核心性质

情形	条件	渐近解	典型示例
情形一	$f(n)=O(n^{{\log }_{b}a-\epsilon })$	$\Theta (n^{{\log }_{b}a})$	$T(n)=2T(n/2)+O(1)\to \Theta (n)$
情形二	$f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$	$\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$	$T(n)=2T(n/2)+O(n)\to \Theta (n\log n)$
情形三	$f(n)=\Omega (n^{{\log }_{b}a+\epsilon })$	$\Theta (f(n))$	$T(n)=3T(n/3)+O(n^2)\to \Theta (n^2)$

应用场景

主定理用于分析各类分治算法的递推关系：

算法	递推关系	适用情形	复杂度
归并排序	$T(n)=2T(n/2)+\Theta (n)$	情形二	$\Theta (n\log n)$
Strassen	$T(n)=7T(n/2)+\Theta (n^2)$	情形一	$O(n^{\lg 7})$
二分搜索	$T(n)=T(n/2)+\Theta (1)$	情形一	$\Theta (\log n)$
快速排序（最坏）	$T(n)=T(n-1)+\Theta (n)$	不适用	$\Theta (n^2)$

参见

• 递归关系式 — 主定理求解的对象
• 递归树 — 主定理的直观推导工具
• 分治法 — 产生此类递推关系的算法策略
• 归并排序 — 主定理的经典应用案例
• Strassen算法 — 主定理情形一的应用