主定理
分析算法複雜度的方法,從遞歸式得出通項的大小估計
在演算法分析中,主定理(英语:Master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由乔恩·本特利、多萝西·布洛斯坦和詹姆斯·B·萨克斯在1980年提出,在那里被描述为解决这种递推的“天下无敌法”(Master method)。此方法经由经典演算法教科书托马斯·H·科尔曼、查尔斯·E·雷瑟尔森、罗纳德·李维斯特和克利福德·史坦的《算法导论》推广而为人熟知。
不过,并非所有递推关系式都可应用支配理论。该定理的推广形式包括阿克拉-巴兹方法。
支配理论
假设有递归关系式
- ,其中
其中, 为问题规模, 为递归的子问题数量, 为每个子问题的规模(假设每个子问题的规模基本一样), 为递归以外进行的计算工作。
情形一
如果存在常数 ,有
- (可不严谨的视作多项式地小于)
则
情形二
如果存在常数 ,有
则
情形三
如果存在常数 ,有
- (多项式地大于)
同时存在常数 以及充分大的 ,满足
则
常用演算法中的应用
演算法 | 递回关系式 | 运算时间 | 备注 |
---|---|---|---|
二分搜寻演算法 | 情形二( ) | ||
二叉树遍历 | 情形一 | ||
最佳排序矩阵搜索(已排好序的二维矩阵) | |||
合并排序 | 情形二( ) |
参考文献
- 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.