1.4.4　递归算法的复杂性分析

1．递归算法的时间复杂性分析

一般而言，计算一个递归算法的时间复杂性可以遵循以下步骤：

（1）决定采用哪个（或哪些）参数作为输入规模的度量。

（2）找出对算法的运行时间贡献最大的语句作为基本语句。

（3）检查一下，对于相同规模的不同输入，基本语句的执行次数是否不同。如果不同，则需要从最好、最坏及平均三种情况进行讨论。

（4）对于选定的基本语句的执行次数建立一个递推关系式，并确定停止条件。

（5）通过计算该递推关系式得到算法的渐进时间复杂性。

计算递推关系式的方法有很多，最常用的便是后向代入法。该方法是从n出发，利用递推关系，把n表示成n-1的函数关系，而n-1可以表示成n-2的函数关系，以此类推，直到停止条件为止。一般可以得到一个连加的形式，求解该连加式的值就可以得到渐进意义下的时间复杂性。

【例1-7】　以1.4.3节的排列问题为例讨论如何分析递归算法的时间复杂性。

不难发现，当k=1时，已构成一个排列，第一个for循环需要执行n次操作将排列输出；当k=n时，第二个for循环的循环体，对perm（A，k-1，n）执行n次调用。因此，排列算法perm对应的递归定义式为

采用后向代入法计算可得到通项公式，计算过程如下：

T（n）=nT（n-1）+nO（1）

=n（n-1）T（n-2）+n（n-1）O（1）+nO（1）

=n（n-1）（n-2）T（n-3）+n（n+1）（n-2）O（1）+n（n-1）O（1）+nO（1）

=…

=n（n-1）（n-2）…2T（1）n（n-1）（n-2）…2O（1）+…+nO（1）

=O（n!O（n（n-1）…2）+…+O（n）

所以，全排列算法perm的时间复杂性为Ω（n!）。

2．递归算法的空间复杂性分析

递归算法的空间复杂性指的是算法的递归深度，即算法在执行过程中所需的用于存储“调用记录”的递归栈的空间大小。

上述计算T（n）的过程共执行了n次递推，可见perm算法的递归深度为n，由此可得，perm算法所需的递归栈的空间为O（n）。

另外，人们也常常采用构建递归树的方法来对递归算法进行复杂性分析。这种方法较为方便且直观形象，多年的实践也证明了它是一个较好的分析工具。实际上，递归树的思想是用树来反映递归函数调用的次序，根结点代表主程序，其他结点代表所调用的子函数。算法运行时所需要的空间与递归树的高度紧密相关——成正比，而树中的结点数则反映了执行算法的关键步骤所需的时间。