递归算法的数学分析

本节中，我们会了解到如何系统地运用通用框架来分析算法递归算法的效率。让我们用一个例子介绍递归算法的概念。

例1 对于非负整数n，计算阶乘函数F(n) = n!的值。

考虑到，当n ≧ 1时，n! = 1·…·(n-1)·n＝(n-1)!·n

并且根据定义，0!=1, 故使用下面的递归算法计算F(n)=F(n-1)·n.

算法 F(n)
    //递归计算n!
    //输入：非负整数n
    //输出：n!的值
    if n = 0 return 1
    else return F(n-1)*n

简单起见，算法的输入规模为n。算法的基本操作是乘法，执行次数记作M(n). 因为函数F(n)的计算公式是

当n>0时，F(n) = F(n-1)·n

乘法常量M(n)满足这个等式：

当n>0时，M(n) = M(n-1) + 1

其中，M(n-1):用于计算F(n-1), 最后加1是指将F(n-1)乘以n

计算F(n-1)需要用M(n-1)次乘法，还有一次乘法用来把结果乘n。

最后一个等式定义了M(n)的一个值序列。这个等式没有明确地定义M(n),即没有把它定义为n的函数，而是定义成它本身在另一个点(n-1)上的值的函数，这种等式称为递推关系，或者简称递推式.

现在的目标是解递推关系M(n)=M(n-1)+1.为了确定一个唯一解，还需要一个初始条件得到该序列的起始值，观察该算法停止递归调用时的条件

if n=0 return 1

这个语句告诉我们两个信息。第一，调用在n＝0时结束，故算法能够处理的n的最小值和M(n)定义域上的最小值都是0.第二，当n＝0时，该算法不执行乘法操作。所以，我们所遵循的初始条件是：

M(0) = 0

递归调用在n＝0时停止，当n＝0的时候不做乘法操作。

这样，我们成功地建立了关于该算法的乘法次数M(n)的递推关系和初始条件：

当n>0时，M(n)=M(n-1)+1 (2.2)
M(0)=0

在解决这个递推式以前，我们重申一个要点。我们现在处理的是两个递归定义的函数。第一个是阶乘函数F(n)本身：它是由下列递推式定义的：

当n>0时，F(n) = F(n-1)·n
F(0) = 1

第二个函数利用该递归算法计算F(n)的过程中，所要执行的乘法次数——M(n).M(n)是由递推式(2.2)定义的。而我们现在要解的正是递推式(2.2).

我们用反向替换法，解这个特定递推式。

M(n) = M(n-1) + 1 替换M(n-1) = M(n-2) + 1
= [M(n-2)+1]+1=M(n-2)+2 替换M(n-2) = M(n-3) + 1
= [M(n-3)+1]+2=M(n-3)+3

用一个通用方程来描述该模式：M(n)=M(n-i)+i.

剩下需要做的是利用给定的初始条件。该条件针对的是n=0，故在模式的方程中把i替换为n(n-i=0 => i=n), 得到我们反向替换的最终结果：

M(n)=M(n-1)+1=…=M(n-i)+i=…=M(n-n)+n=n

与一个对n个连续整数累乘的循环算法相比，循环算法需要执行同样次数的乘法，但它在不必花费额外的时间和空间维护递归栈。

归纳一下研究递归阶乘书算法的经验，我们描绘出研究递归算法的一个一般性方案。

分析递归算法效率的通用方案

  1. 决定用哪个参数作为输入规模的度量。
  2. 找出算法的基本操作。
  3. 考虑对于相同规模的不同输入，基本操作的执行次数是否不同。如果不同，则必须对最差效率，平均效率以及最优效率作单独研究。
  4. 对于算法基本操作的执行次数，建立一个递归关系以及相应的初始条件。
  5. 解这个递推式，确定它的解的增长次数。

例2 汉诺塔游戏.游戏中，有n个不同大小的盘子和3根木桩。开始时，所有的盘子都按照大小顺序套在第一根木桩上，最大的盘子在底部，最小的盘子在顶部。我们目的是把所有的盘子都移到第3根木桩上去，可以借助第二根木桩，每次只能移动一个盘子，但是不能把较大的盘子放在较小的盘子的上面。

这个问题有一个优雅的递归解法，图2.4描述了这个解法。

我们需要先把n-1个盘子递归地从木桩1移到木桩2，然后直接把最大的盘子从木桩1移到木桩3，最后把n-1个盘子递归地从木桩2移到木桩3.当然，如果n=1,我们可以简单地把这个单独的盘子直接从一个木桩移到另一个木桩。

我们选择盘子的数量n作为输入规模的一个指标，盘子的移动作为该算法的基本操作。我们看到，移动的次数M(n)只依赖于n，对于M(n)我们有下列递推等式：

当n>1时，M(n)=M(n-1)+1+M(n-1)
M(1)=1

我们使用反向替换法来解这个递推式：

M(n)=2M(n-1)+1 替换M(n-1)=2M(n-2)+1
=2[2M(n-2)+1]+1=2^2M(n-2)+2+1 替换M(n-2)=2M(n-3)+1
=2^2[M(n-3)+1]+2+1=2^3M(n-3)+2^2+2+1

左边前3个求和算式的模式预示着下一个算式将是：2^4M(n-4)+2^3+2^2+2+1,对这个模式进行一般化处理，在做了i次替换以后，我们有：

M(n)=2^iM(n-i)+2^(i-1)+2^(i-2)+…+2+1=2^iM(n-i)+2^i-1

初始条件是在n＝1，故i=n-1(n-i => i=n-1)，得到下列方程：

M(n)=2^(n-1)M(n-(n-1))+2^(n-1)-1
=2^(n-1)M(1)+2^(n-1)-1
=2^n-1

这样我们得到了一个指数级的算法，算法的运行时间长的无法想象。这个例子揭示了一个重要观点：

我们应该谨慎使用递归算法，因为它们的简洁可能会掩盖它们的低效率。

一个递归算法不止一次地调用它本身，出于分析的目的，构造一课它的递归调用树。在这棵树中，节点相当于递归调用，我们用调用参数的值作为节点的标记。汉诺塔的递归调用树如图2.5。

通过计算树中的节点数，我们得到汉诺塔算法所做调用的全部次数：

例3 一个十进制正整数在二进制表示中的二进制数字的个数的递归版本。

算法 BinRec(n)
    //输入：一个正的十进制整数n
    //输出：n的二进制表示位数
    if n=1 return 1
    else return BinRec([n/2]) + 1

计算该算法所做的加法次数A(n), BinRec([n/2]),所做的加法次数是A([n/2]), 该算法把返回值加1的时候，执行的加法次数也增加一。因此，我们可以得出下面这个递推式：

当n>1时，A(n)=A([n/2])+1

当n＝1时递归调用结束，加法的次数不再增加，所以，初始条件是:

A(1) = 0

函数的参数包含[n/2], 如果n不是2的乘方，就很难应用反向替换法。标准的做法是仅在n＝2^k的情况下对该递推式求解，然后再使用平滑规则定理。定理认为，在一个非常宽泛的假设下，无论n取何值，它的增长次数与n＝2^k时的增长次数完全相同。应用平滑规则定理，对于n=2^k, 递推式成为了这种形式：

当k>0时，A(2^k)=A(2^(k-1))+1
A(2^0)=0

现在，反向替换法就不会遇到困难了：

A(2^k)=A(2^(k-1))+1 替换A(2^(k-1))=A(2^(k-2))+1
=[A(2^(k-2))+1]+1=A(2^(k-2))+2 替换A(2^(k-2))=A(2^(k-3))+1
=[A(2^(k-3))+1]+2=A(2^(k-3))+3
…
=A(2^(k-i))+i
…
=A(2^(k-k))+k

这样，在结束时我们有

A(2^k)=A(1)+k=k

转换成原来的变量n的函数。n＝2^k，所以k=log2 n

下一节我们专门讨论斐波那契数；对它们的分析涉及更复杂的递推关系和一个不同于反向替换法的额解决方法。

Loading Disqus comments...
Table of Contents