主定理

在算法分析中，主定理（英语：Master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由乔恩·本特利、多萝西·布洛斯坦（英语：Dorothea Blostein）和詹姆斯·B·萨克斯（英语：James B. Saxe）在1980年提出，在那里被描述为解决这种递推的“天下无敌法”（Master method）。此方法经由经典算法教科书托马斯·H·科尔曼（英语：Thomas H. Cormen）、查尔斯·E·雷瑟尔森（英语：Charles E. Leiserson）、罗纳德·李维斯特（英语：Ron Rivest）和克利福德·史坦（英语：Clifford Stein）的《算法导论》推广而为人熟知。

不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括阿克拉-巴兹方法（英语：Akra–Bazzi method）。

支配理论

假设有递归关系式

${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$，其中 ${\displaystyle a\geq 1{\mbox{, }}b>1}$

其中，${\displaystyle n}$为问题规模，${\displaystyle a}$为递归的子问题数量，${\displaystyle {\frac {n}{b}}}$为每个子问题的规模（假设每个子问题的规模基本一样），${\displaystyle f(n)}$为递归以外进行的计算工作。

情形一

如果存在常数${\displaystyle \epsilon >0}$，有

${\displaystyle f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right)}$（可不严谨的视作多项式地小于）

则

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

情形二

如果存在常数${\displaystyle \epsilon \geq 0}$，有

${\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon }n\right)}$

则

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon +1}n\right)}$

情形三

如果存在常数${\displaystyle \epsilon >0}$，有

${\displaystyle f(n)=\Omega \left(n^{\log _{b}(a)+\epsilon }\right)}$（多项式地大于）

同时存在常数${\displaystyle c<1}$以及充分大的${\displaystyle n}$，满足

${\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}$

则

${\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}$

常用算法中的应用

算法	递回关系式	运算时间	备注
二分搜索算法	${\displaystyle T(n)=T\left({\frac {n}{2}}\right)+\Theta (1)}$	${\displaystyle \Theta (\log n)}$	情形二（${\displaystyle \epsilon =0}$）
二叉树遍历	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+\Theta (1)}$	${\displaystyle \Theta (n)}$	情形一
最佳排序矩阵搜索（已排好序的二维矩阵）	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)}$	${\displaystyle \Theta (n)}$
归并排序	${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+\Theta (n)}$	${\displaystyle \Theta (n\log n)}$	情形二（${\displaystyle \epsilon =0}$）

参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Sections 4.3 (The master method) and 4.4 (Proof of the master theorem), pp. 73–90.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.