计算机科学

首页 > 计算机科学

主定理

2018-08-28 09:51:05     所属分类:算法分析

在算法分析中,主定理英语:master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery,Dorothea Haken和James B. Saxe在1980年提出,在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen,Leiserson,Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。

不过,并非所有递推关系式都可应用主定理。该定理的推广形式包括Akra-Bazzi定理。

目录

  • 1 主定理
    • 1.1 情形一
    • 1.2 情形二
    • 1.3 情形三
  • 2 常用算法中的应用
  • 3 参考文献

主定理

假设有递推关系式

,其中

其中,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.

上一篇:算法分析
下一篇:大O符号
相关推荐