主定理

演算法分析中,支配理论(英語:master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery英语Jon Bentley (computer scientist)Dorothea Haken英语Dorothea HakenJames B. Saxe英语James B. Saxe在1980年提出,在那里被描述为解决这种递推的“天下無敵法”(master method)。此方法经由经典演算法教科书Cormen英语Thomas H. CormenLeiserson英语Charles E. LeisersonRivest英语Ron RivestStein的《算法导论》 (introduction to algorithm) 推广而为人熟知。

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

支配理论编辑

假设有递归关系式

 ,其中  

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

情形一编辑

如果存在常数 ,有

 (可不嚴謹的視作多项式地小于)

 

情形二编辑

如果存在常数 ,有

 

 

情形三编辑

如果存在常数 ,有

 (多项式地大于)

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

 

 

常用演算法中的应用编辑

演算法 递回关系式 运算时间 备注
二分搜尋演算法     情形二( 
二叉树遍历     情形一
最佳排序矩阵搜索(已排好序的二维矩阵)    
合并排序     情形二( 

参考文献编辑

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