主定理

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

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

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

，其中 

其中，为问题规模，为递归的子问题数量，为每个子问题的规模（假设每个子问题的规模基本一样），为递归以外进行的计算工作。

 情形一 
如果存在常数，有

（可不嚴謹的視作多项式地小于）

则

 情形二 
如果存在常数，有

则

 情形三 
如果存在常数，有

（多项式地大于）

同时存在常数以及充分大的，满足

则

 常用演算法中的应用 
 演算法 递回关系式 运算时间 备注 二分搜尋演算法  情形二（） 二叉树遍历   情形一最佳排序矩阵搜索（已排好序的二维矩阵） 情形一 合併排序  情形二（）

 参考文献 
 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.

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