第四章 分治策略 4.4 用递归树方法求解递归式

  在递归树中，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。   递归树最适合用来生成好的猜测，然后即可用代入法来验证猜测是都正确。当使用递归树来生成好的猜测时，常常需要忍受一点儿“不精确”，因为稍后才会验证猜测是否正确。如果在画递归树和代价求和时非常仔细，就可以用递归树直接证明解是否正确。

  以递归式 T ( n ) = 3 T ( ⌊ n / 4 ⌋ ) + c n 2 T(n)=3T(\lfloor n/4\rfloor)+cn^2 T(n)=3T(⌊n/4⌋)+cn2 为例，如图所示：

  对递归式 T ( n ) = 3 T ( ⌊ n / 2 ⌋ ) + n T(n)=3T(\lfloor n/2\rfloor)+n T(n)=3T(⌊n/2⌋)+n ，利用递归树确定一个好的渐近上界，用代入法进行验证。

  解：图略。递归树的层数为： lg ⁡ n + 1 \lg n +1 lgn+1 ，     第 i i i 层的代价符合通式： ( 3 / 2 ) i − 1 n (3/2)^{i-1}n (3/2)i−1n ，     叶子的树目为 n lg ⁡ 3 n^{\lg 3} nlg3 ，     猜测渐近上界为 O ( n lg ⁡ 3 ) O(n^{\lg3}) O(nlg3) ，下面使用代入法证明：     当 n = 1 n = 1 n=1， T ( 1 ) = 1 ≤ 1 lg ⁡ 3 T(1) = 1 ≤ 1^{\lg3} T(1)=1≤1lg3 。     假设当 n < m n < m n2a​    故渐近上界为 O ( n 2 ) O(n^2) O(n2) 。     假设当 n < m n < m n-c/(αlgα+(1-α)lg(1-α))​    故渐近上界为 O ( n lg ⁡ n ) O(n\lg n) O(nlgn) 。     假设当 n < m n < m n