《算法导论》三种解递归式的方法

作者: Sun东辉 | 来源:发表于2022-06-10 10:07 被阅读0次

代入法

步骤

猜测解的形式；
用数学归纳法求出解中的常数，并证明解是正确的。

代入法可以用来确定一个递归式的上界或下界。这种方法很有效，但只能用于解的形式很容易猜的情形。

例如，我们需要确定下面递归式的上界：

$T(n) = 2T(n/2)+n$

该递归式与归并排序相似，我们可以猜测其解为

$T(n)=O(nlgn)$

代入法要求证明，恰当选择常数 c>0，可有 T(n)≤cn lgn。首先假设此上界对所有正数 m<n 都成立，特别是对于 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。将其代入递归式，得到：

$T(n)\leq2(c\frac n2\lg\left(\frac n2\right))+n\leq cn\;\lg\left(\frac n2\right)+n\;=\;cn\;\lg\left(n\right)\;-\;cn\lg\left(2\right)+n\;=\;cn\;\lg\left(n\right)-cn+n\leq cn\;\lg\left(n\right)$

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

如何做一个好的猜测

并不存在通用的方法来猜测递归式的正确解，但总有一些试探法可以帮助做出好的猜测：

如果某个递归式与先前见过的类似，则可猜测该递归式有类似的解。如，递归式

$T(n) = 2T(\frac{n}{2}+17)+n$

看起来比较难解，因为右式 T 的自变量中加了 17，但我们可以猜测这个多出来的项对解的影响不大，因为当 n 很大时， $T(\frac{n}{2})$ 与 $T(\frac{n}{2}+17)$ 之间的差别并不大，两者都将 n 分成均匀的两半。

另一种方法是先证明递归式的较松的上下界，然后再缩小不确定性区间。例如，对递归式 $T(n)=2T(\frac{n}{2})+n$ ，因为递归式中有 n，而我们可以证明初始上界为 $T(n)=O(n^2)$ 。然后，逐步降低其上界，提高其下界，直到达到正确的渐近确界 $T(n)=\Theta(n \lg n)$ 。

一些细微问题

有时，我们或许能够猜出递归式解的渐近界，但却会在归纳证明时出现一些问题。通常，问题出在归纳假设不够强，无法证明其准确的界，遇到这种情况时，可以去掉一个低阶项来修改所猜测的界，以使证明顺利进行。如下面的递归式：

$T(n)=2T(\frac{n}{2})+1$

可以猜测其解为 $O(n)$ ，即要证明对适当选择的 c，有 $T(n)\leq cn$ 。有所猜测的界对递归式做替换，得到

$T(n)\leq cn+1$

由此无法得到 $T(n)\leq cn$ ，无论 c 的值如何。如果猜测一个更大的界，如 $T(n)=O(n^2)$ ，虽然这确实是上界，但事实上，所猜测的解 $T(n)=O(n)$ 却是正确的。为了证明这一点，要做一个更强的归纳假设。

从直觉上说，猜测 $T(n)=O(n)$ 几乎是正确的，只是差了一个常数 1，即一个低阶项，然而，就因为差了一项，数学归纳法就无法证明出期望的结果。从所作的猜测中减去一个低阶项，即 $T(n) \leq cn-b, b\geq0$ 是个常数。现在有

$T(n)\leq cn-2b+1 \leq cn-b$

只要 b≥ 1。这里，c 要选的足够大，以便能处理边界条件。

你可能会觉得从所作的猜测中减去一项有点儿与直觉不符。为什么不是增加一项来解决问题呢？关键在于要理解我们是在用数学归纳法：通过对更小的值作更强的假设，就可以证明对某个给定值的更强的结论。

避免陷阱

在运用渐近表示时很容易出错。例如，对递归式 $T(n)=2T(\frac{n}{2})+n$ ，由假设 $T(n)\leq cn$ ，并证明

$T(n) \leq 2c\frac{n}{2} \leq cn+n = O(n)$

就是错误的，因为 c 是常数，因而错误地证明了 $T(n)=O(n)$ 。错误在于没有证明归纳假设的准确形式，即 $T(n) \leq cn$ 。

改变变量

有时，对一个陌生的递归式作一些简单的代数变换，就会使之变成读者较熟悉的形式。如下例子：

$T(n)=2T(\sqrt n)+\lg n$

这个式子看上去比较难，但可以对它进行简化，方法是改动变量。为了方便起见，不考虑数的截取整数问题，如将 $\sqrt{n}$ 化为整数。设 $m=\lg n$ ，得

$T(2^m) = 2T(2^{\frac{m}{2}})+m$

再设 $S(m)=T(2^m)$ ，得到新的递归式

$S(m)=2S(\frac{m}{2})+m$

这个式子看起来与 $T(n)=2T(\frac{n}{2})+n$ 就非常像了，这个新的递归式的界是： $S(m)=O(m \lg m)$ 。将 $S(m)$ 带回 $T(n)$ ，有 $T(n)=T(2^m)=S(m)=O(m \lg m)=O(\lg n \lg \lg n)$ 。

递归树

有时候，画出一个递归树是一种得到好猜测的直接方法。在递归树中，每一个节点都代表递归函数调用集合中一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加，得到的结果是所有层次的总代价。当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。

递归树最适合用来产生好的猜测，然后用代入法加以验证。但使用递归树产生好的猜测时，通常可以容忍小量的“不良量”，因为稍后就会证明所做的猜测。如果画递归树时非常地仔细，并且将代价都加了起来，那么就可以直接用递归树作为递归式的解的证明。

在讲述例子之前，我们先来看一个几何级数公式

对于实数 x≠1，式

$\sum_{k=0}^nx^k=1+x+x^2+...+x^n$

是一个几何级数（或称指数级数），其值为

$\sum_{k=0}^nx^k=\frac{x^{n+1}-1}{x-1}$

当和是无限的且 |x|<1 时，有无限递减几何级数

$\sum_{k=0}^\infty x^k=\frac1{1-x}$

例如：

我们以递归式

$T(n)=3T(n/4)+\Theta(n^2)$

为例来看一下如何用递归树生成一个好的猜测。首先关注如何寻找解的一个上界，因为我们知道舍入对求解递归式通常没有影响（此处即是我们需要忍受不精确的一个例子），因此可以为递归式

$T(n)=3T(n/4)+cn^2$

创建一颗递归树，其中已将渐近符号改写为隐含的常数系数 c>0。

构造的递归树如下：

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

$T(n)\;=\;cn^2+\frac3{16}cn^2+\left(\frac3{16}\right)^2cn^2+...+\left(\frac3{16}\right)^{\log_4\left(n-1\right)}cn^2+\Theta(n^{\log_4\left(3\right)})=\sum_{i=0}^{\log_4\left(n-1\right)}\left(\frac3{16}\right)^icn^2+\Theta(n^{\log_4\left(3\right)})=\frac{\left({\displaystyle\frac3{16}}\right)^{\log_4\left(n\right)}-1}{{\displaystyle\frac3{16}}-1}cn^2+\Theta(n^{\log_4\left(3\right)})$

最后的这个公式看起来不够整洁，但我们可以再次充分利用一定程度的不精确，并利用无限递减几何级数作为上界。回退一步，得到：

$T(n)\;=\;\sum_{i=0}^{\log_4\left(n-1\right)}\left(\frac3{16}\right)^icn^2+\Theta(n^{\log_4\left(3\right)})<\sum_{i=0}^\infty\left(\frac3{16}\right)^icn^2+\Theta(n^{\log_4\left(3\right)})=\frac1{1-{\displaystyle\frac3{16}}}cn^2+\Theta(n^{\log_4\left(3\right)})=\frac{16}{13}cn^2+\Theta(n^{\log_4\left(3\right)})=O(n^2)$

此时，我们得到了递归式的一个猜测，在上面的例子里， $cn^2$ 系数形成了一个递减的等比级数，可知这些系数的总和的上界是常数 $\frac{16}{13}$ 。由于树根所需的代价为 $cn^2$ ，所以根部的代价占总代价的一个常数部分。换句话说，整棵树的总代价是由根部的代价所决定的。

事实上，如果 $O(n^2)$ 确实是此递归式的上界，那么它一定是确界，为什么呢？第一个递归调用所需要的代价是 $\Theta(n^2)$ ，所以 $\Omega(n^2)$ 一定是此递归式的下界。

现在我们可以使用代换法来验证猜测的正确性， $T(n)=O(n^2)$ 是递归式 $T(n)=3T(\frac{n}{4})+\Theta(n^2)$ 的一个上界。只需要证明，当某常数 d>0， $T(n) \leq dn^2$ 成立。适用与前面相同的常数 c>0，有

$T(n) \leq 3T(\frac{n}{4})+cn^2 \leq 3d{\frac{4}{4}}^2 + cn^2 \leq 3d{\frac{n}{4}}^2 + cn^2 = \frac{3}{16}dn^2+cn^2 \leq dn^2$

只要 d≥ $\frac{16}{13}c$ ，最后一步都会成立。

一个较复杂的例子

上图是递归式

$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+O(n)$

对应的递归树。我们还是使用 c 来代表 $O(n)$ 项常数因子。当将递归树内各层的数值加起来时，可以得到每一层的 cn 值。从根部到叶子的最长路径是 $n \rightarrow \frac{2}{3}n \rightarrow (\frac{2}{3})^2n \rightarrow ... \rightarrow 1$ 。因为当 $k= \log_\frac32\left(n\right)$ 时， $(\frac{2}{3})^kn=1$ ，所以树的深度是 $\log_\frac32\left(n\right)$ 。

直觉上，我们预期递归式的解至多是层数乘以每层的代价，也就是 $O(cn \log_\frac32\left(n\right)) = O(n \lg n)$ 。总代价被均匀地分布到递归树内的每一层上。这里还有一个复杂点：我们还没有考虑叶子的代价。如果这棵树是高度为 $\log_\frac32\left(n\right)$ 的完整二叉树，那么有 $2^{\log_\frac32\left(n\right)}=n^{\log_\frac32\left(2\right)}$ 个叶子节点。由于叶子代价是常数，因此所有叶子代价的总和为 $\Theta(n^{\log_\frac32\left(2\right)})$ ，或者说 $\omega(n \lg n)$ 。然而，这棵递归树并不是完整的二叉树，少于 $n^{\log_\frac32\left(2\right)}$ 个叶子，而且从树根往下的过程中，越来越多的内部结点在消失。因此，并不是所有层次都刚好需要 cn 代价；越靠近底层，需要的代价越少。我们可以计算出准确的总代价，但记住我们只是想要找出一个猜测来使用到代入法中。让我们容忍这些误差，而来证明上界为 $O(n \lg n)$ 的猜测是正确的。

事实上，可以用代入法来证明 $O(n \lg n)$ 是递归式解的上界。下面证明 $T(n) \leq dn \lg n$ ，当 d 是一个合适的正值常数，则

$T(n)\leq T(\frac n3)+T(\frac{2n}3)+cn\;\leq d\frac n3lg\frac n3+d\frac{2n}3lg\frac{2n}3+cn=(d\frac n3lgn-d\frac n3lg3)+(d\frac{2n}3lgn-d\frac{2n}3lg3)+cn=dn\;lgn-d(\frac n3lg3+\frac{2n}3lg\frac32)+cn=dn\;lgn-d(\frac n3lg3+\frac{2n}3lg3-\frac{2n}3lg2)+cn=dn\;lgn-dn(lg3-\frac23)+cn\leq dn\;lgn$

上式成立的条件是 $d \geq \frac{c}{\lg3-\frac{2}{3}}$ 。因此，没有必要去更准确地计算递归树中的代价。

主方法

“食谱”

主方法给出了求解递归式的“食谱”方法，即将规模为 n 的问题划分为 a 个子问题的算法的运行时间，每个子问题规模为 $\frac{n}{b}$ ，a 和 b 是正常数。a 个子问题被分别递归地解决，时间各为 $T(\frac{n}{b})$ 。划分原问题和合并答案的代价由函数 $f(n)$ 描述。

从技术正确性角度来看，递归式实际上没有得到很好的定义，因为 $\frac{n}{b}$ 可能不是一个整数。但用 $T(\frac{n}{b})$ 向上取整或向下取整来代替 a 项 $T(\frac{n}{b})$ 并不影响递归式的渐近行为，因而，在写分治算法时略去向下取整和向上取整函数会带给很大的方便。

主方法依赖于主定理：令 a≥1 和 b>1 是常数，f(n) 是一个函数，T(n)是定义在非负数整数上的递归式：

$T(n)=aT(n/b)+f(n)$

其中我们将 n/b 解释为 n 除以 b 的向下取整或向上取整。那么 T(n) 有如下渐近界：

若对某个常数 $\varepsilon$ >0 有 f(n) =O( $n^{\log_b\left(a-\varepsilon\right)}$ )，则 T(n)= $\Theta$ ( $n^{\log_b\left(a\right)}$ )。
若 f(n)= $\Theta$ ( $n^{\log_b\left(a\right)}$ )，则 T(n)= $\Theta$ ( $n^{\log_b\left(a\right)} \lg n$ )。
若对某个常数 $\varepsilon$ >0 有 f(n)= $\Omega(n^{\log_b\left(a+\varepsilon\right)})$ ，且对某个常数 c<1 和所有足够大的 n 有 af(n/b)≤cf(n)，则 T(n)= $\Theta$ (f(n))。

在使用主定理之前，我们需要花一点时间尝试理解它的含义。对于三种情况的每一种，将函数 f(n) 与函数 $n^{\log_b\left(a\right)}$ 进行比较。直觉上，两个函数较大者决定了递归式的解。若函数 $n^{\log_b\left(a\right)}$ 更大，如情况 1，则解为 T(n)= $\Theta$ ( $n^{\log_b\left(a\right)}$ )。若函数 f(n) 更大，如情况 3，则解为 T(n)= $\Theta$ (f(n))。若两个函数大小相当，如情况 2，则乘上一个对数因子，解为 T(n)= $\Theta$ ( $n^{\log_b\left(a\right)} \lg n$ )= $\Theta$ ( $f(n)\lg n$ )。

另外还有一些技术问题需要加以理解。在第一种情况下，不仅要有 $f(n)$ 小于 $n^{\log_b\left(a\right)}$ ，还必须是多项式地小于，也就是说， $f(n)$ 必须渐近小于 $n^{\log_b\left(a\right)}$ ，要相差一个因子 $n^ \varepsilon$ ，其中 $\varepsilon$ 是大于 0 的常数。在第三种情况下，不是 $f(n)$ 大于 $n^{\log_b\left(a\right)}$ 就够了，而是要多项式意义上的大于，而且还要满足“正则”条件 $af(\frac{n}{b}) \leq cf(n)$ 。

注意：三种情况并没有覆盖所有可能的 f(n)。当 f(n) 只是小于 $n^{\log_b\left(a\right)}$ 但不是多项式地小于时，在第一种情况和第二种情况之间就存在一条“沟”。类似情况下，当 f(n) 大于 $n^{\log_b\left(a\right)}$ ，但不是多项式地大于时，第二种情况和第三种情况之间就会存在一条“沟”。如果 f(n) 落在任一条“沟”中，或是第三种情况种规则性条件不成立，则主方法就不能用于解递归式。

使用主方法

使用主方法很简单，首先确定主定理的哪种情况成立，即可得到解。

例如：

$T(n)=9T(n/3)+n$

对于这个递归式，我们有 a=9，b=3，f(n)=n，因此 $n^{\log_b\left(a\right)}$ = $n^{\log_3\left(9\right)}$ = $\Theta(n^2)$ 。由于 f(n) = $O(n^{\log_3\left(9-\varepsilon\right)})$ ，其中 $\varepsilon = 1$ ，因此可以应用于主定理的情况 1，从而得到解 T(n) = Θ( $n^2$ ) 。

现在考虑

$T(n) = T(2n/3) + 1$

其中，a = 1， b = 3/2， f(n) = 1，因此 $n^{\log_b\left(a\right)}$ = $n^{\log_{3/2}\left(1\right)}$ = $n^0$ = 1 。由于 f(n) = $\Theta(n^{\log_b\left(a\right)})$ = Θ(1) ，因此可应用于情况2，从而得到解 T(n) = Θ( $\lg n$ ) 。

对于递归式

$T(n) = 3T(n/4) + nlgn$

我们有 a = 3，b = 4，f(n) = nlgn，因此 $n^{\log_b\left(a\right)}$ = $n^{\log_4\left(3\right)}$ =O( $n^{0.793}$ )。由于 $f(n)=\Omega(n^{\log_4\left(3-\varepsilon\right)})$ 当 n，其中 $\varepsilon \approx 0.2$ ，因此，如果可以证明正则条件成立，即应用于情况 3。当 n 足够大时，对于 $c = \frac{3}{4}$ ， $af(\frac{n}{b})=3\frac{n}{4} \lg \frac{n}{4} \leq \frac{3}{4}n \lg n = cf(n)$ ，因此，由情况 3，递归式的解为 T(n)= $\Theta$ ( $n\lg n$ )。

主方法不能用于如下递归式：

$T(n) = 2T(\frac{n}{2})+n \lg n$

虽然这个递归式看起来有恰当的形式：a=2，b=2， $f(n)=n \lg n$ ，以及 $n \lg_b{a} = n$ 。你可能错误地认为应该应用情况 3，因为 $f(n)= n \lg n$ 渐近大于 $n^{log_b{a}}=n$ 。问题出现在它并不是多项式意义上的大于。对任意正常数 $\varepsilon$ ，比值 $\frac{f(n)}{n^{log_b{a}}} = \frac{n \lg n}{n} = \lg n$ 都渐近小于 $n^\varepsilon$ 。因此，递归式落入了情况 2 和情况 3 之间的间隙。

主方法证明

证明分为两部分。第一部分分析“主”递归式 $T(n)=aT(\frac{n}{b})+f(n)$ ，并作了简化假设 $T(n)$ 仅定义在 b>1 的整数幂上，即 $n=1$ ， $b$ ， $b^2$ ，…。这部分从直觉上说明该定理为什么是正确的。第二部分说明如何将分析扩展至对所有的正整数 n 都成立，主要是应用数学技巧来解决向下取整函数和向上取整函数的处理问题。

取正合幂时的证明

对于递归式

$T(n)=aT(\frac{n}{b})+f(n)$

此时的假设是 n 为 b>1 的正合幂，且 b 不必是整数。分析可分成三个引理说明，第一个引理是将解原递归式的问题归约为对一个含和式的求值的问题。第二个引理决定含和式的界，第三个引理把前两个合在一起，证明当 n 为 b 的正合幂时主定理成立。

引理一：设 a≥1，b>1 为常数，f(n) 为定义在 b 的正合幂上的非负函数。定义 $T(n)$ 如下：

$T(n)=\left\{\begin{array}{l}\Theta(1)\;\;\;\;\;\mathrm{如果}n=1\\aT(\frac nb)+f(n)\;\;\mathrm{如果}\;n=b^i\end{array}\right.$

其中 i 是正整数，则有

$T(n)=\Theta(n^{\log_ba})+\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$

证明：如下图。根节点代价为 f(n)，它有 a 个子女，每个代价是 $f(\frac{n}{b})$ 。（为方便起见可将 a 视为整数，但这对数学推导没什么影响。）每个子女又各有 a 个子女，代价为 $f(\frac{n}{b^2})$ 。这样就有 $a^2$ 个结点离根的距离为 2。一般地，距根为 j 的结点有 $a^j$ 个，每一个的代价为 $f(\frac{n}{b^j})$ 。每一个叶结点的代价为 $T(1)=\Theta(1)$ ，每一个都距根 $\log_bn$ ，因为 $\frac{n}{b^{\log_ba}}=1$ 。树中共有 $a^{\log_bn}=n^{\log_ba}$ 个叶结点。

可以将树中各层上的代价加起来而得到方程 $T(n)=\Theta(n^{\log_ba})+\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$ ，第 j 层上内部结点的代价为 $a^jf(\frac{n}{b^j})$ ，故各层内部结点的总代价和为

$\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$

在其所基于的分治算法中，这个和值表示了将问题分解成为子问题并将子问题的解合并时所花的代价，所有叶子的代价（即解 $n \log_ba$ 个规模为 1 的子问题的代价）为 $\Theta(n^{\log_ba})$ 。

根据递归树，主定理的三种情况对应于树中总代价的三种情况：1、由所有叶子节点的代价决定；2、均匀分布在各层上；3、由根结点的代价决定。

引理二：设 a≥1，b≥1 为常数， $f(n)$ 为定义在 b 的整数幂上的非负函数。函数 $g(n)$ 由下式定义

$g(n)=\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$

对 b 的整数幂，该函数可被渐近限界为：

若对常数 $\varepsilon>0$ ，有 $f(n)=O(n^{\log_ba-\varepsilon})$ ，则 $g(n)=O(n^{\log_ba})$ 。
若 $f(n)=\Theta(n^{\log_ba})$ ，则 $g(n)=\Theta(n^{\log_ba}\lg n)$ 。
若对常数 c<1 及所有的 n≥b， $af(\frac{n}{b})\leq cf(n)$ ，则 $g(n)=\Theta(f(n))$ 。

证明：对情况 1，有 $f(n)=O(n^{\log_ba-\varepsilon})$ ，这隐含着 $f(\frac{n}{b^i})=O({\frac{n}{b^j}}^{\log_ba-\varepsilon})$ 。用它对方程 $g(n)=\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$ 做代换，得

$g(n)=O(\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;(\frac n{b^j})^{\log_b{a-\varepsilon}}}})$

对 O 标记内的式子限界，方法是提出不变项并作简化，得到一个上升几何级数：

$\sum_{j=0}^{\log_bn-1}a^j{(\frac n{b^j})}^{\log_ba-\varepsilon}=n^{\log_ba-\varepsilon}\sum_{j=0}^{\log_bn-1}{(\frac{ab^\varepsilon}{b^{\log_ba}})}^j=n^{\log_ba-\varepsilon}\sum_{j=0}^{\log_bn-1}{(b^\varepsilon)}^j=n^{\log_b\left(a-\varepsilon\right)}(\frac{b^\varepsilon\log_bn-1}{b^\varepsilon})=n^{\log_b\left(a-\varepsilon\right)}(\frac{n^\varepsilon-1}{b^\varepsilon-1})$

因为 b 与 $\varepsilon$ 都是常数，最后的表达式可化简为 $n^{\log_b{a-\varepsilon}}O(n^{\varepsilon})=O(n^{\log_ba})$ 。用此表达式对 $g(n)=O(\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;(\frac n{b^j})^{\log_b{a-\varepsilon}}}})$ 作替换，得

$g(n)=O(n^{\log_ba})$

情况 1 得以验证。

为证情况 2，假设 $f(n)=\Theta(n^{\log_ba})$ ，有 $f(\frac{n}{b^j})=\Theta(\frac{n}{b^j})^{\log_ba}$ 。用此式对方程 $g(n)=\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$ 作替换，得

$g(n)=\Theta(\sum_{j=0}^{\log_bn-1}a^j{(\frac n{b^j})}^{\log_ba})$

对 $\Theta$ 记号中的式子做类似情况 1 中的限界，但所得并非是几何级数，而是每项都是相同的:

$\Theta(\sum_{j=0}^{\log_bn-1}a^j{(\frac n{b^j})}^{\log_ba})=n^{\log_ba}\sum_{j=0}^{\log_bn-1}{(\frac a{b^{\log_ba}})}^j=n^{\log_ba}\sum_{j=0}^{\log_bn-1}1=n^{\log_ba}\log_bn$

用此方程对 $g(n)=\Theta(\sum_{j=0}^{\log_bn-1}a^j{(\frac n{b^j})}^{\log_ba})$ 中的和式做替换，有

$g(n)=\Theta(n^{\log_ba}\log_bn)=\Theta(n^{\log_ba}\lg n)$

则情况 2 得以验证。情况 3 也可以用类似的方式证明。

引理三：设 a≥1，b>1 是常量， $f(n)$ 是定义在 b 的整数幂上的非负函数。定义 T(n) 如下：

$T(n)\;=\;\left\{\begin{array}{l}\Theta(1)\;\;\mathrm{如果}\;n=1\\aT(\frac nb)+f(n)\;\;\mathrm{如果}\;n=b^i\end{array}\right.$

其中 i 是正整数。对于 b 的整数幂，T(n) 可有如下渐近界：

若 $f(n)=O(n^{\log_b{a-\varepsilon}})$ ， $\varepsilon>0$ ，则 $T(n)=\Theta(n^{\log_ba})$ 。
若 $f(n)=\Theta(n^{\log_ba})$ ，则 $T(n)=\Theta(n^{\log_ba}lg\;n)$
若 $f(n)=\Omega(n^{\log_ba+\varepsilon})$ ， $\varepsilon>0$ ，且若对常数 $c<1$ ，和所有足够大的 n， $af(\frac{n}{b})\leq cf(n)$ ，则 $T(n)=\Theta(f(n))$ 。

证明：用引理二给出的界来对引理一中的式 $T(n)=\Theta(n^{\log_ba})+\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$ 求值。对情况 1 有

$T(n) = \Theta(n^{\log_ba})+O(n^{\log_ba})=\Theta(n^{\log_ba})$

对情况 2 有

$T(n) = \Theta(n^{\log_ba})+\Theta(n^{\log_ba}\lg n)=\Theta(n^{\log_ba}\lg n)$

对情况 3 有

$T(n)=\Theta(n^{\log_ba})+\Theta(f(n))=\Theta(f(n))$

因为 $f(n)=\Omega(n^{\log_ba+\varepsilon})$ 。

向上取整函数和向下取整函数

为使主定理的证明更完整，还要将分析扩展到主递归式中含上取整函数和下取整函数的情形，从而使递归式定义在所有整数上，而不仅仅是定义在 b 的整数幂上。

如上图，用 $n_j$ 来表示序列中第 j 个元素，即

$n_j=\left\{\begin{array}{l}n\;\;\;\mathrm{如果}\;j=0\\n_j-\frac1b\;\mathrm{如果}\;j\;>0\;\end{array}\right.$

我们的第一个目标是决定使 $n_k$ 为常数的深度 k。利用不等式 x≤x+1，得

$n_0 \leq n, n_1 \leq \frac{n}{b}+1 , n_2 \leq \frac{n}{b^2}+\frac{1}{b}+1, n_3 \leq \frac{n}{b^3}+\frac{1}{b^2}+\frac{1}{b}+1,...$

一般地

$n_j\;\leq\frac n{b^j}+\sum_{i=0}^{j-1}\frac1{b^i}<\frac n{b^j}+\sum_{i=0}^\infty\frac1{b^j}+\frac b{b-1}$

当 $j=\log_bn$ 时，有

$n\log_bn\;=\;\frac n{b^{\log_bn}}+\frac b{b-1}\leq\frac n{b^{\log_b\left(n-1\right)}}+\frac b{b-1}=\frac{n^2}b+\frac b{b-1}=b+\frac b{b-1}=O(1)$

所以我们发现在深度为 $\log_bn$ 时，问题大小至多为常数。

从上图中我们得到

$T(n)=\Theta(n^{\log_ba})+\sum_{j=0}^{\log_b\left(a\right)-1}a^jf(n_j)$

这个式子和

$T(n)=\Theta(n^{\log_ba})+\overset{\log_bn-1}{\underset{j=0}{\sum a^j\;f(\frac n{b^j})}}$

很相似，只是此处 n 可以是任意整数，而不限于 b 的整数幂。

现在利用类似于引理二的证明方法对 $T(n)=\Theta(n^{\log_ba})+\sum_{j=0}^{\log_b\left(a\right)-1}a^jf(n_j)$ 和 $g(n)=\sum_{j=0}^{\log_b\left(a\right)-1}a^jf(n_j)$ 求值，先看情况 3，如果 n>b+b/(b-1)，有 af(n/b)≤cf(n),c<1 为常数，则 $a^jf(n_j) \leq c^jf(n)$ 。这样， $g(n)=\sum_{j=0}^{\log_b\left(a\right)-1}a^jf(n_j)$ 中的和式就可如引理二一样地求值。对情况 2，有 f(n)= $\Theta(n^{log_ba})$ 。如果我们能证明 $f(n_j)=O(n^\frac{\log_ba}{a^j})=O(\frac{n}{b^j}^{\log_ba})$ ，则套用引理二的中情况 2 的证明即可。注意这时有 $j \leq \log_bn$ 隐含着 $\frac{b^j}{n} \leq 1$ 。界 $f(n)=O(n^{\log_ba})$ 隐含着存在常数 c>0，使对足够大的 $n_j$ ，有

$f(n_j)\leq c{(\frac n{b^j}+\frac b{b-1})}^{\log_ba}=c{(\frac n{b^j}(1+\frac{b^j}n\times\frac b{b-1}))}^{\log_ba}=c(\frac{n^{\log_ba}}{a^j})(1+{(\frac{b^j}n\times\frac b{b-1}))}^{\log_ba}\leq c(\frac{n^{\log_ba}}{a^j}){(1+\frac b{b-1})}^{\log_ba}=O(\frac{n^{\log_ba}}{a^j})$

此处 $c(1+b(b-1))^{\log_ba}$ 是个常数，如此情况 2得以验证。情况 1的证明几乎一样，关键在于证明界 $f(n_j)=O(n^{\log_b{a-\varepsilon}})$ ，这与情况 2 中对应部分的证明类似，但代数运算要更复杂。

到这里我们证明了对于整数 n 主定理的上界，其下界的证明也类似。

《算法导论》三种解递归式的方法

代入法

步骤

如何做一个好的猜测

一些细微问题

避免陷阱

改变变量

递归树

例如：

一个较复杂的例子

主方法

“食谱”

主方法依赖于主定理：令 a≥1 和 b>1 是常数，f(n) 是一个函数，T(n)是定义在非负数整数上的递归式：

使用主方法

主方法证明

向上取整函数和向下取整函数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法导论