《算法导论》第四章 续2

4.3 用代入法求解递归式

我们已经看到如何用递归式刻画分治算法的运行时间，下面将学习如何求解递归式。我们从“代入”法开始。

代入法求解递归式分为两步：

1. 猜测解的形式。

2. 用数学归纳法求出解中的常数，并证明解是正确的。

当将归纳假设应用于较小的值时，我们将猜测的解代入函数，因此得名“代入法”。这种方法很强大，但我们必须能猜出解的形式，以便将其代入。

我们可以用代入法为递归式建立上界或下界。例如，我们确定下面递归式的上界：

该递归式与递归式(4.3)和(4. 4)相似。我们猜测其解为T(n) =O(nlgn)。代入法要求证明，恰当选择常数c>0，可有T(n)≤cn lgn。首先假定此上界对所有正数m<n都成立，特别是对于m=「n/2」，有T(「n/2」)≤c 「n/2」lg(「n/2」)。将其代入递归式，得到

其中，只要c≥1，最后一步都会成立。

数学归纳法要求我们证明解在边界条件下也成立。为证明这一点，我们通常证明对于归纳证明，边界条件适合作为基本情况。对递归式(4.19)，我们必须证明，通过选择足够大的常数c，可以使得上界T(n)≤cn lgn对边界条件也成立。这一要求有时可能引起问题。例如，为了方便讨论，假设T(1)=1是递归式唯一的边界条件。 对n=1，边界条件T(n)≤cn lgn推导出T(1)≤c1lg1=0，与T(1)=1矛盾。因此，我们的归纳证明的基本情况不成立。

我们稍微多付出一点努力，就可以克服这个障碍，对特定的边界条件证明归纳假设成立。例如，在递归式(4. 19)中，渐近符号仅要求我们对n≥n_o证明T(n)≤cnlgn，其中n_o是我们可以自己选择的常数，我们可以充分利用这一点。我们保留麻烦的边界条件T(1)=1，但将其从归纳证明中移除。为了做到这一点，首先观察到对于n>3，递归式并不直接依赖T(1)。因此，将归纳证明中的基本情况T(1)替换为T(2)和T(3)，并令n_o=2。注意，我们将递归式的基本情况(n=1)和归纳证明的基本情况(n=2和n=3)区分开来了。由T(1)=1，从递归式推导出T(2)=4和T(3)=5。现在可以完成归纳证明：对某个常数c≥1，T(n)≤cnlgn， 方法是选择足够大的c，满足T(2)≤c2lg2和T(3)≤c3lg3。事实上，任何c≥2都能保证n=2和n=3的基本情况成立。对于我们所要讨论的大多数递归式来说，扩展边界条件使归纳假设对较小的n成立，是一种简单直接的方法，我们将不再总是显式说明这方面的细节。

做出好的猜测

遗憾的是，并不存在通用的方法来猜测递归式的正确解。猜测解要靠经验，偶尔还需要创造力。幸运的是，你可以使用一些启发式方法帮助你成为一个好的猜测者。你也可以使用递归树来做出好的猜测，我们将在4.4节看到这一方法。

如果要求解的递归式与你曾见过的递归式相似，那么猜测一个类似的解是合理的。例如，考虑如下递归式：

看起来很困难，因为在等式右边T的参数中增加了“17”。但直观上，增加的这一项不会显著影响递归式的解。当n较大时，「n/2」和「n/2」+ 17的差距不大：都是接近n的一半。因此，我们猜测T(n)=O(nlgn)，你可以使用代入法验证这个猜测是正确的(见练习4. 3-6)。

另一种做出好的猜测的方法是先证明递归式较松的上界和下界，然后缩小不确定的范围。例如，对递归式(4. 19)，我们可以从下界T(n)=Ω(n)开始，因为递归式中包含n这一项，还可以证明一个初始上界T(n)=O(n²)。然后，我们可以逐渐降低上界，提升下界，直至收敛到渐近紧确界T(n) =Θ(nlgn)。

微妙的细节

有时你可能正确猜出了递归式解的渐近界，但莫名其妙地在归纳证明时失败了。问题常常出在归纳假设不够强，无法证出准确的界。当遇到这种障碍时，如果修改猜测，将它减去一个低阶的项，数学证明常常能顺利进行。

考虑如下递归式：

我们猜测解为T(n)=O(n)，并尝试证明对某个恰当选出的常数c，T(n)≤cn 成立。将我们的猜测代入递归式，得到

这并不意味着对任意c都有T(n)≤cn.我们可能忍不住尝试猜测一个更大的界，比如T(n) =O(n²)。虽然从这个猜测也能推出结果，但原来的猜测T(n)=O(n)是正确的。然而为了证明它是正确的，我们必须做出更强的归纳假设。

直觉上，我们的猜测是接近正确的：只差一个常数1，一个低阶项。但是，除非我们证明与归纳假设严格一致的形式，否则数学归纳法还是会失败。克服这个困难的方法是从先前的猜测中减去一个低阶项。新的猜测为T(n)≤cn-d，d是大于等于0的一个常数。我们现在有

只要d≥1，此式就成立。与以前一样，我们必须选择足够大的c来处理边界条件。

你可能发现减去一个低阶项的想法与直觉是相悖的。毕竟，如果证明上界失败了，就应该将猜测增加而不是减少，更松的界难道不是更容易证明吗？不一定！当利用归纳法证明一个上界时，实际上证明一个更弱的上界可能会更困难一些，因为为了证明-一个更弱的上界，我们在归纳证明中也必须使用同样更弱的界。在当前的例子中，当递归式包含超过一个递归项时，将猜测的界减去一个低阶项意味着每次对每个递归项都减去一个低阶项。在上例中，我们减去常数d两次，一次是对T(「n/2」）项，另一次是对T(「n/2」)项。我们以不等式T(n)≤cn-2d+1结束，可以很容易地找到一个d值，使得cn-2d+1小于等于cn-d。

避免陷阱

使用渐近符号很容易出错。例如，在递归式(4. 19)中，我们可能错误地“证明"T(n) = O(n)：猜测T(n)≤cn，并论证

因为c是常数。错误在于我们并未证出与归纳假设严格一致的形式，即T(n)≤cn。因此，当要证明T(n)=O(n)时，需要显式地证出T(n)≤cn。

改变变量

有时，一个小的代数运算可以将-个未知的递归式变成你所熟悉的形式。例如，考虑如下递归式：

它看起来很困难。但我们可以通过改变变量来简化它。为方便起见，我们不必担心值的舍人误差问题，只考虑√n是整数的情形即可。令m= lgn，得到

现在重命名S(m)= T(2^m)，得到新的递归式：

它与递归式(4.19)非常像。这个新的递归式确实与(4.19)具有相同的解：S(m)=O(mlgm)。再从S(m)转换回T(n)，我们得到T(n)= T(2^m)= S(m) =O(m lgm) =O(lgn lg lgn)。

练习

4.3-1  证明：T(n)= T(n-1)+n的解为O(n²)。

4.3-2  证明：T(n)= T(「n/2」) +1的解为O(lgn)。

4.3-3  我们看到 T(n)=2T(「n/2」) +n的解为O(nlgn)。证明Ω(nlgn)也是这个递归式的解。从而得出结论：解为Θ(nlgn)。

4.3-4  证明：通过做出不同的归纳假设，我们不必调整归纳证明中的边界条件，即可克服递归式(4.19)中边界条件T(1)=1带来的困难。

4.3-5  证明：归并排序的“严格”递归式(4. 3)的解为Θ(nlgn)。

4.3-6  证明：T(n) =2T(「n/2」+17)+n的解为O(n lgn)。

4.3-7  使用 4.5节中的主方法，可以证明T(n)= 4T(n/3)+n的解为T(n)= Θ(n^log₃ ⁴)。说明基于假设T(n)≤cn^log₃ ⁴的代入法不能证明这一结论。然后说明如何通过减去一个低阶项完成代入法证明。

4.3-8  使用4. 5节中的主方法，可以证明T(n) =4T(n/2)+n的解为T(n)=Θ(n²)。说明基于假设T(n)≤cn²的代入法不能证明这一结论。然后说明如何通过减去一个低阶项完成代入法证明。

4.3-9  利用改变变量的方法求解递归式T(n) = 3T(√n) +logn。你的解应该是渐近紧确的。不必担心数值是否是整数。

4.4 用递归树方法求解递归式

虽然你可以用代入法简洁地证明一个解确是递归式的正确解，但想出一个好的猜测可能会很困难。画出递归树，如我们在2. 3.2节分析归并排序的递归式时所做的那样，是设计好的猜测的一种简单而直接的方法。在递归树中，每个结点表示一个单一子问题的代价， 子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。

递归树最适合用来生成好的猜测，然后即可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常需要忍受一点儿“不精确”，因为稍后才会验证猜测是否正确。但如果在画递归树和代价求和时非常仔细，就可以用递归树直接证明解是否正确。在本节中，

我们将使用递归树生成好的猜测，并且在4.6节中，我们将使用递归树直接证明主方法的基础定理。

我们以递归式T(n)=3T(「n/4」) +Θ(n²)为例来看一下如何用递归树生成一个好的猜测。首先关注如何寻找解的一个上界。因为我们知道舍入对求解递归式通常没有影响（此处即是我们需要忍受不精确的一个例子)，因此可以为递归式T(n)=3T(「n/4」)+cn²创建一棵递归树，其中已将渐近符号改写为隐含的常数系数c>0。

图4-5显示了如何从递归式T(n)=3T(「n/4」) +cn²构造出递归树。为方便起见，我们假定n是4的幂(忍受不精确的另一个例子)，这样所有子问题的规模均为正数。图4-5(a)显示了T(n)，它在图4-5(b)中扩展为一棵等价的递归树。根结点中的cn²项表示递归调用顶层的代价，根的三棵子树表示规模为n/4的子问题所产生的代价。图4-5(c)显示了进一步构造递归树的过程，将图4-5(b)中代价为T(n/4)的结点逐一扩展。我们继续扩展树中每个结点，根据递归式确定的关系将其分解为几个组成部分（孩子结点)。

图4-5    为递归式 T(n)= 3T(「n/4」) +cn²构造递归树。(a)显示了T(n)， 在(b)~(d)中逐步扩展为递归树的形式。

                                                      (d)中显示了扩展完毕的递归树，其高度为log₄n(有log₄n+1层)

因为子问题的规模每一步减少为上一步的1/4，所以最终必然会达到边界条件。那么根结点与距离为1的子问题距离多远呢？深度为i的结点对应规模为n/4ⁱ的子问题。因此，当n/4ⁱ=1，或等价地i=log₄n时，子问题规模变为1。因此，递归树有log₄n+1层(深度为0, 1, 2, ...，log₄n)。

接下来确定树的每一层的代价。每层的结点数都是上一层的3倍，因此深度为i的结点数为3ⁱ。因为每一层子问题规模都是上一层的1/4，所以对i=0，1, 2,  log₄n-1, 深度为i的每个结点的代价为c(n/4ⁱ)²。做一下乘法可得，对i=0，1, 2, ... ，log₄n-1，深度为i的所有结

点的总代价为3ⁱc(n/4)²=(3/16)ⁱcn²。树的最底层深度为log₄n，有3^{log4 n}=nk83个结点，每个结点的代价为T(1)，总代价为n^log₄ ³T(1)，即Θ(n^log₄³)，因为假定T(1)是常量。

现在我们求所有层次的代价之和，确定整棵树的代价：

最后的这个公式看起来有些凌乱，但我们可以再次充分利用一定程度的不精确，并利用无限递减几何级数作为上界。回退一步，应用公式(A. 6)，我们得到

这样，对原始的递归式T(n)=3T(「n/4」)+Θ(n²)，我们推导出了一个猜测T(n)=O(n²)。在本例中，cn²的系数形成了一个递减几何级数，利用公式(A.6)，得出这些系数的和的一个上界——常数16/13。由于根结点对总代价的贡献为cn²，所以根结点的代价占总代价的一个常数

比例。换句话说，根结点的代价支配了整棵树的总代价。

实际上，如果O(n²)确实是递归式的上界(稍后就会证明这一点)，那么它必然是一个紧确界。为什么？因为第一次递归调用的代价为Θ(n²)，因此Ω(n²)必然是递归式的一个下界。

现在用代入法验证猜测是正确的，即T(n)=O(n²)是递归式T(n)=3T(「n/4」) +Θ(n²)的一个上界。我们希望证明T(n)≤dn²对某个常数d>0成立。与之前一样，使用常数c>0，我们有

图4-6 递归式 T(n)= T(n/3)+ T(2n/3)+cn

当d≥(16/13)c时，最后一步推导成立。在另一个更复杂的例子中，图4-6显示了如下递归式的递归树：

T(n) = T(n/3)+ T(2n/3) + O(n)

(为简单起见，再次忽略了舍人问题。)与之前一样，令c表示O(n)项中的常数因子。对图中显示出的递归树的每个层次，当求代价之和

时，我们发现每层的代价均为cn。从根到叶的最长简单路径是n→>(2/3)n→(2/3)²n→...→1。由于当k=log_3/2n时，(2/3)^kn=1， 因此树高为log_3/2n。

直觉上，我们期望递归式的解最多是层数乘以每层的代价，即O(cn log_3/2n)=O(nlgn)。但图4-6仅显示了递归树的顶部几层，并不是递归树中每个层次的代价都是cn。考虑叶结点的代价。如果递归树是一棵高度为log_3/2n的完全二叉树，则叶结点的数量应为

2^log_3/2ⁿ=n^log_3/2²。 由于每个叶结点的代价为常数，因此所有叶结点的总代价为Θ(n^log_3/2²)，由于log_3/2n是严格大于1的常数，因此叶结点代价总和为Ω(nlgn)。但递归树并不是完全二叉树，因此叶结点数量小于n^log_3/2²。而且，当从根结点逐步向下走时，越来越多的内结点是缺失的。因此，递归树中靠下的层次对总代价的贡献小于cn。我们可以计算出所有代价的准确值，但记住我们只是希望得到一个猜测，用于代入法。我们还是忍受一些不精确，尝试证明猜测的上界O(n lgn)是正确的。

我们确实可以用代入法验证O(nlgn)是递归式解的一个上界。我们来证明T(n)≤dn lgn，其中d是一个适当的正常数。我们有

只要d≥c/(lg3- (2/3))。 因此，无需对递归树的代价进行更精确的计算。

练习

4.4-1  对递归式 T(n)=3T(「n/2」)+n，利用递归树确定一个好的渐近上界，用代入法进行验证。

4.4-2  对递归式 T(n)= T(n/2)+n²，利用递归树确定一个好的渐近上界，用代入法进行验证。

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

4.4-4  对递归式 T(n)= T(n-1)+1，利用递归树确定一个好的渐近上界，用代入法进行验证。

4.4-5  对递归式 T(n)=T(n- 1)+ T(n/2) +n，利用递归树确定一个好的渐近上界，用代入法进行验证。

4.4-6  对递归式 T(n)= T(n/3) + T(2n/3)+cn，利用递归树论证其解为Ω(nlgn)，其中c为常数。

4.4-7  对递归式 T(n)=4T(Ln/2]) +cn(c为常数)，画出递归树，并给出其解的一个渐近紧确界。用代入法进行验证。

4.4-8  对递归式 T(n)= T(n-a) + T(a)+cn，利用递归树给出一个渐近紧确解，其中a≥1和c>0是常数。

4.4-9  对递归式 T(n)= T(am)+ T((1-a)n) +cn，利用递归树给出一个渐近紧确解，其中0<a<1和c>0是常数。