主定理

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

演算法分析中,主定理(英語: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.