递归方程求解的方法

    2.1.4　递归方程求解的方法

    算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。

    递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法：

    ①代入法

    这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。

    ②迭代法

    这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。

    ③套用公式法

    这个方法针对形如：T (n)=aT (n / b)+f (n)的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。

    ④差分方程法

    有些递归方程可以看成一个差分方程，因而可以用解差分方程（初值问题）的方法来解递归方程。然后对得到的解作渐近阶的估计。

    ⑤母函数法

    这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。