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