Loading AI tools
分析算法複雜度的方法,從遞歸式得出通項的大小估計 来自维基百科,自由的百科全书
在演算法分析中,主定理(英語:Master theorem)提供了用漸近符號(大O符號)表示許多由分治法得到的遞推關係式的方法。這種方法最初由喬恩·本特利、多蘿西·布洛斯坦和詹姆斯·B·薩克斯在1980年提出,在那裡被描述為解決這種遞推的「天下無敵法」(Master method)。此方法經由經典演算法教科書托馬斯·H·科爾曼、查爾斯·E·雷瑟爾森、羅納德·李維斯特和克利福德·史坦的《算法導論》推廣而為人熟知。
不過,並非所有遞推關係式都可應用支配理論。該定理的推廣形式包括阿克拉-巴茲方法。
假設有遞歸關係式
其中,為問題規模,為遞歸的子問題數量,為每個子問題的規模(假設每個子問題的規模基本一樣),為遞歸以外進行的計算工作。
如果存在常數,有
則
如果存在常數,有
則
如果存在常數,有
同時存在常數以及充分大的,滿足
則
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.