主定理

分析算法複雜度的方法,從遞歸式得出通項的大小估計

算法分析中,主定理(英语:Master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由乔恩·本特利多萝西·布洛斯坦英语Dorothea Blostein詹姆斯·B·萨克斯英语James B. Saxe在1980年提出,在那里被描述为解决这种递推的“天下无敌法”(Master method)。此方法经由经典算法教科书托马斯·H·科尔曼英语Thomas H. Cormen查尔斯·E·雷瑟尔森英语Charles E. Leiserson罗纳德·李维斯特英语Ron Rivest克利福德·史坦英语Clifford Stein的《算法导论》推广而为人熟知。

不过,并非所有递推关系式都可应用支配理论。该定理的推广形式包括阿克拉-巴兹方法英语Akra–Bazzi 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.