主定理

在演算法分析中，主定理（英語：Master theorem）提供了用漸近符號（大O符號）表示許多由分治法得到的遞推關係式的方法。這種方法最初由喬恩·本特利、多蘿西·布洛斯坦和詹姆斯·B·薩克斯在1980年提出，在那裏被描述為解決這種遞推的「天下無敵法」（Master method）。此方法經由經典演算法教科書托馬斯·H·科爾曼、查爾斯·E·雷瑟爾森、羅納德·李維斯特和克利福德·史坦的《演算法導論》推廣而為人熟知。

不過，並非所有遞推關係式都可應用支配理論。該定理的推廣形式包括阿克拉-巴茲方法。

支配理論

假設有遞歸關係式

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

其中，$n$為問題規模，$a$為遞歸的子問題數量，${\frac {n}{b}}$為每個子問題的規模（假設每個子問題的規模基本一樣），$f(n)$為遞歸以外進行的計算工作。

情形一

如果存在常數$\epsilon >0$，有

$f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right)$（可不嚴謹的視作多項式地小於）

則

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

情形二

如果存在常數$\epsilon \geq 0$，有

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

則

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

情形三

如果存在常數$\epsilon >0$，有

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

同時存在常數$c<1$以及充分大的$n$，滿足

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

則

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

常用演算法中的應用

演算法	遞迴關係式	運算時間	備註
二分搜尋演算法	$T(n)=T\left({\frac {n}{2}}\right)+\Theta (1)$	$\Theta (\log n)$	情形二（$\epsilon =0$）
二叉樹遍歷	$T(n)=2T\left({\frac {n}{2}}\right)+\Theta (1)$	$\Theta (n)$	情形一
最佳排序矩陣搜尋（已排好序的二維矩陣）	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$\Theta (n)$
合併排序	$T(n)=2T\left({\frac {n}{2}}\right)+\Theta (n)$	$\Theta (n\log n)$	情形二（$\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.