在演算法分析中,主定理(英語:Master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由喬恩·本特利、多蘿西·布洛斯坦和詹姆斯·B·薩克斯在1980年提出,在那里被描述为解决这种递推的“天下無敵法”(Master method)。此方法经由经典演算法教科书托馬斯·H·科爾曼、查爾斯·E·雷瑟爾森、羅納德·李維斯特和克利福德·史坦的《算法导论》推广而为人熟知。
不过,并非所有递推关系式都可应用支配理论。该定理的推广形式包括阿克拉-巴茲方法。
假设有递归关系式
,其中 ![{\displaystyle a\geq 1{\mbox{, }}b>1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8987ae7ed923d97980c6d1e5e6ee91e0f28a40c5)
其中,
为问题规模,
为递归的子问题数量,
为每个子问题的规模(假设每个子问题的规模基本一样),
为递归以外进行的计算工作。
如果存在常数
,有
(可不嚴謹的視作多项式地小于)
则
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceb5444d7cb63715b7588d60e302cd6481723cf0)
如果存在常数
,有
![{\displaystyle f(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon }n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/281efc107407d5c0720d12dd7e4a40e8d1362223)
则
![{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log ^{\epsilon +1}n\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b1407dd42b9dc7ef13acdcf9e1545fb51070c16)
如果存在常数
,有
(多项式地大于)
同时存在常数
以及充分大的
,满足
![{\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90e16559ef4aac0ab33033fd25bf0a5a50d21a0a)
则
![{\displaystyle T\left(n\right)=\Theta \left(f\left(n\right)\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed4853d676dfac75faed7777f19b695ee51f865b)
演算法 | 递回关系式 | 运算时间 | 备注 |
二分搜尋演算法 | | | 情形二( ) |
二叉树遍历 | | | 情形一 |
最佳排序矩阵搜索(已排好序的二维矩阵) | | | |
合併排序 | | | 情形二( ) |
- 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.