主定理

维基百科,自由的百科全书
跳转至: 导航搜索

算法分析中,主定理英语:master theorem)提供了用渐近符号表示许多由分治法得到的递推关系式的方法。此方法经由经典算法教科书《算法导论》而为人熟知。不过,并非所有递推关系式都可应用主定理。该定理的推广形式包括Akra-Bazzi定理

主定理[编辑]

假设有递推关系式

,其中

其中,n为问题规模,a为递推的子问题数量,n/b为每个子问题的规模(假设每个子问题的规模基本一样),f(n)为递推以外进行的计算工作。

情形一[编辑]

如果存在常数,有

,并且是多项式的小于


那么

情形二[编辑]

如果存在常数k ≥ 0,有

那么

情形三[编辑]

如果存在常数,有

,并且是多项式的大于

同时存在常数以及充分大的,满足

那么

常用算法中的应用[编辑]

算法 递推关系式 运算时间 备注
折半搜索 情形二(k = 0)
二叉树遍历 情形一
归并排序 情形二(k = 0)

参考文献[编辑]

  • 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.