主定理

Template:NoteTA 在演算法分析中，主定理（Template:Lang-en）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由喬恩·本特利、Template:Le和Template:Le在1980年提出，在那里被描述为解决这种递推的“天下無敵法”（Master method）。此方法经由经典演算法教科书Template:Le、Template:Le、羅納德·李維斯特和Template:Le的《算法导论》推广而为人熟知。

不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括Template:Le。

支配理论

假设有递归关系式

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$，其中 $a\ge 1\text{, }b>1$

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

情形一

如果存在常数$ϵ>0$，有

$f(n)=O\left(n^{{\log }_b(a)-ϵ}\right)$（可不嚴謹的視作多项式地小于）

则

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

情形二

如果存在常数$ϵ\ge 0$，有

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

则

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

情形三

如果存在常数$ϵ>0$，有

$f(n)=\mathrm{\Omega }\left(n^{{\log }_b(a)+ϵ}\right)$（多项式地大于）

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

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

则

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

常用演算法中的应用

演算法	递回关系式	运算时间	备注
二分搜尋演算法	$T(n)=T\left(\frac{n}{2}\right)+\mathrm{\Theta }(1)$	$\mathrm{\Theta }(\log n)$	情形二（$ϵ=0$）
二叉树遍历	$T(n)=2T\left(\frac{n}{2}\right)+\mathrm{\Theta }(1)$	$\mathrm{\Theta }(n)$	情形一
最佳排序矩阵搜索（已排好序的二维矩阵）	$T(n)=2T\left(\frac{n}{2}\right)+O(\log n)$	$\mathrm{\Theta }(n)$
合併排序	$T(n)=2T\left(\frac{n}{2}\right)+\mathrm{\Theta }(n)$	$\mathrm{\Theta }(n\log n)$	情形二（$ϵ=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.