【20171105】主定理的基本解释整合

时间：2017-11-05 11:50:15 阅读：449 评论：0 收藏：0 [点我收藏+]

在算法分析中，主定理（英语：master theorem）提供了用 渐近符号 表示许多由 分治法 得到的递推关系式的方法。

此方法经由经典算法教科书《算法导论》而为人熟知。不过，并非所有递推关系式都可应用主定理。该定理的推广形式包括Akra-Bazzi定理。

假设有递推关系式

，

其中

为 问题规模，

为递推的子 问题数量，

为 每个子问题的规模（假设每个子问题的规模基本一样），

为 递推以外 进行的 计算工作。

a≥1，b>1为常数，f(n) 为函数，T(n) 为非负整数。

则有以下结果（分类讨论）：

（1）若

那么

（2）若

那么

（3）若

且对于某个常数

和所有充分大的

有

那么

PS：

定义一：Θ（g(n)） = { f(n) | 如果存在正常数c1、c2和正整数n0，使得当n>=n0时，0<c1*g(n)<=f(n)<=c2*g(n)恒成立}

定义二：Ο（g(n)） = { f(n) | 如果存在正常数c和正整数n0，使得当n>=n0时，0<=f(n)<=c*g(n）恒成立}

定义三：Ω（g(n)） = { f(n) | 如果存在正常数c和正整数n0，使得当n>=n0时，0<=c*g(n)<=f(n）恒成立}

原文：http://www.cnblogs.com/CXSheng/p/7786900.html

踩

(0)

评论一句话评论（0）

分享档案

更多>