查看“︁主定理”︁的源代码

{{NoteTA
|G1 = IT
|1 = zh-hans:归并排序; zh-hant:合併排序;
}}
在[[演算法分析]]中，'''主定理'''（{{lang-en|Master theorem}}）提供了用渐近符号（[[大O符号]]）表示许多由[[分治法]]得到的[[递推关系式]]的方法。这种方法最初由[[喬恩·本特利 (計算機科學家)|喬恩·本特利]]、{{le|多蘿西·布洛斯坦|Dorothea Blostein}}和{{le|詹姆斯·B·薩克斯|James B. Saxe}}在1980年提出，在那里被描述为解决这种递推的“天下無敵法”（Master method）。此方法经由经典演算法教科书{{le|托馬斯·H·科爾曼|Thomas H. Cormen}}、{{le|查爾斯·E·雷瑟爾森|Charles E. Leiserson}}、[[羅納德·李維斯特]]和{{le|克利福德·史坦|Clifford Stein}}的《[[算法导论]]》推广而为人熟知。

不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括{{le|阿克拉-巴茲方法|Akra–Bazzi method}}。

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

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

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

=== 情形一 ===
如果存在常数<math>\epsilon > 0</math>，有

:<math>f(n) = O\left( n^{\log_b (a) - \epsilon} \right)</math>（可不嚴謹的視作多项式地小于）

则

:<math>T(n) = \Theta\left( n^{\log_b a} \right)</math>

=== 情形二 ===
如果存在常数<math>\epsilon\ge0</math>，有

:<math>f(n) = \Theta\left( n^{\log_b a} \log^{\epsilon} n \right)</math>

则

:<math>T(n) = \Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right)</math>

=== 情形三 ===
如果存在常数<math>\epsilon > 0</math>，有

:<math>f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right)</math>（多项式地大于）

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

:<math>a f\left( \frac{n}{b} \right) \le c f(n)</math>

则

:<math>T\left(n \right) = \Theta \left(f \left(n \right) \right)</math>

== 常用演算法中的应用 ==
{| class="wikitable"
|-
! 演算法
! 递回关系式
! 运算时间
! 备注
|-
| [[二分搜尋演算法]]
| <math>T(n) = T\left(\frac{n}{2}\right) + \Theta(1)</math>
|<math>\Theta(\log n)</math>
| 情形二（<math>\epsilon=0</math>）
|-
| [[二叉树]]遍历
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(1)</math>
| <math>\Theta(n)</math>
| 情形一
|-
|最佳排序矩阵搜索（已排好序的二维矩阵）
|<math>T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)</math>
|<math>\Theta(n)</math>
|
|-
| [[合併排序]]
| <math>T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(n)</math>
|<math>\Theta(n\log n)</math>
| 情形二（<math>\epsilon=0</math>）
|}

== 参考文献 ==
* 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.&nbsp;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.&nbsp;268–270.

[[Category:渐近分析]]
[[Category:计算复杂性理论]]
[[Category:演算法分析]]