主定理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

演算法分析中,主定理(英語: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 Rivest和Stein的《算法导论》 (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.