主定理

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

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

支配理论
假设有递归关系式

: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\ge0，有

: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 以及充分大的n，满足

:a f\left( \frac{n}{b} \right) \le c f(n)

则

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

常用演算法中的应用
参考文献

• 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.