Massive Algorithms: 关于<<算法导论>>上的主定理（Master Theorem）的证明 - young7的个人空间

1，证明的总体思路

首先，求出递归式的非递归形式，即用多个多项式的和将递归式表示出来
接着，分析这个多项式的和，然后证明之。(证明内部又要分开两个阶段进行)
总之，求出递归式的和式，是证明的开始的基础，所有后续的证明，都要基于这个和式展开的。

首先画出递归树

1）树的高度h

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

(留意f(n)是划分当前问题的代价，也是非叶子节点的代价。

是所有叶子节点的代价，即基本情况的代价的和)

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

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

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

f(n) = O\left( n^{c} \right)

where

c < \log_b a

then:

T(n) = \Theta\left( n^{\log_b a} \right)

Labels