主定理
分析算法複雜度的方法,從遞歸式得出通項的大小估計 / 維基百科,自由的 encyclopedia
在演算法分析中,主定理(英語: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)。