跳至內容

主定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

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