Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 递归方程解的渐近阶的求法
发信站: 哈工大紫丁香 (2002年03月22日14:40:09 星期五), 站内信件

递归方程解的渐近阶的求法
上一章所介绍的递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的
一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的
关键步骤。
递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的
五种方法。
代入法 这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推
测的正确性。那么，显式解的渐近阶即为所求。
迭代法  这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然
后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从
而达到对递归方程解的渐近阶的估计。
套用公式法 这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况
下方程解的渐近阶的三个相应估计公式供套用。
差分方程法  有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)
的方法来解递归方程。然后对得到的解作渐近阶的估计。
母函数法 这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非
齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可
以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一
个关于母函数的可解方程，将其解出，然后返回递归方程的解。
本章将逐一地介绍上述五种井法，并分别举例加以说明。
本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条
件。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]