关于<<算法导论>>上的主定理(Master Theorem)的证明

原创
2014/05/03 20:00
阅读数 1.9W

之前学习《算法导论》关于主定理一章,它的证明是很概略的,网上关于主定理证明的材料不少,但是很多都只局限于在b的幂上的证明,将证明扩展到全体整数的论述相当少。本人查找了不少资料后在这里找到了一篇相对完整的证明(点击这里),但细细读下来却发现它还是有一些瑕疵,因此打算自己补完整个证明,希望能对以后学习算法导论的同学有所帮助。由于本人数学水平不行,如果发现证明有错误或有地方需要补充,欢迎联系我youth7@163.com

 

1,证明的总体思路

首先,求出递归式的非递归形式,即用多个多项式的和将递归式表示出来

接着,分析这个多项式的和,然后证明之。(证明内部又要分开两个阶段进行)

总之,求出递归式的和式,是证明的开始的基础,所有后续的证明,都要基于这个和式展开的。

 

2,递归式的和

首先画出递归树




这里介绍一下几个变量是怎么来的

1)树的高度h

这里需要重点理解的是,从这个和式我们可以直观地感受到,如果两个部分中谁的阶数较高,则谁决定和式的上界。因此接着的具体证明就是围绕着这两部分的大小关系展开的。我们有以下几种情况:

(留意f(n)是划分当前问题的代价,也是非叶子节点的代价。 是所有叶子节点的代价,即基本情况的代价的和)

1)如果第一部分比第二部分的阶数要高,这意味着递归树的总代价由叶子的代价决定

2)如果两部分相等,这意味着递归树的总代价分布均匀,由叶子节点和其它节点共同决定

3)如果第二部分阶数比第一部分要高,这意味着递归树的总代价由内层叶子决定,也即是说,划分问题的代价决定递归树的总代价

理解三种情形的现实意义很重要,它能帮助我们清晰体会到递归式的本质


3,证明的第1阶段

第一阶段的证明并不是在全体自然数上进行的,而是将n定义在b的幂上面,即 ,以下是证明过程

一阶段情况1




一阶段情况2



一阶段情况3



综合上述,第一阶段证明完毕


4,证明的第2阶段

第二阶段是在第一阶段的基础上,将主定理的定义域由 扩展到从全体自然数上,但是有两点必须注意:


二阶段情况1

二阶段情况2



二阶段情况3


5,扩展

我们可以看到,其实主定理是不能覆盖所有情况的,主定理的本质是递归式,递归式的求解有很长历史,算法导论的本章注记中谈到了Akra-Bazzi方法(个人认为是一种关于递归式的普遍性解法),有兴趣可以参考一下附录参考资料228,这种方法能够解决任何递归问题。

Tom Leighton. Notes on better master theorems for divide-and-conquer recurrences. Class notes. Available at http://citeseer.ist.psu.edu/252350.html, October 1996.

由于网页编辑器不支持公式,只能贴图片,完整高清版已经上传新浪资料,有需要可以自行搜索下载,希望这个证明不会误导各位朋友。

最近发现新浪资料已经暂时关闭了,悲剧啊,上传百度文档的话又不能识别公式,有推荐的地方吗?

展开阅读全文
加载中
点击加入讨论🔥(11) 发布并加入讨论🔥
打赏
11 评论
4 收藏
1
分享
返回顶部
顶部