跳转到内容

主定理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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