算法分析中经常遇到需要求解递推式的情况,即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为 因为递推式求解的重要性,许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。 在这些相关论述中,主要介绍了一些启发式方法,这些方法往往需要一些特殊的技巧和灵感才能完成。 而本文将论述一种纯代数式的方法,这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组,这样就使得整个求解过程不依赖于太多技巧,因此具有更好的易用性。 本文首先会给出两个例子:如何使用纯代数方法求解斐波那契数列和汉诺塔递推式;然后会借助线性代数论述这种方法背后的数学意义,说明线性递推式与线性方程的内在联系以及这种解法的数学原理;最后将例子中的方法推广到一般情况。 示例例1:斐波那契数列斐波那契数列大家应该很熟悉了,这里不再赘述,直接进入问题。 问题设斐波那契数列为由如下递推式定义的数列:
求解 求解首先忽略初始条件,考虑递推式
这样问题被转化为一个一元二次方程的求根问题。利用求根公式可得:
因此得到递推式的一个通解:
即其中
解得
例2:汉诺塔汉诺塔的时间复杂度通常使用递归式定义,在这个例子中将使用代数方法求解其封闭形式。 问题汉诺塔的时间复杂度为 求解这里并不能直接使用例1中的方法,因为右边除了递推项外,还有一个非递推项1,用线性代数的语言说,这个线性递推式是非齐次的。 可以回想一下线性代数中求解非齐次方程组通解的方法:1)求解其齐次部分的通解。2)求其一个特解,将特解加到通解上即得非齐次方程组通解。 我们用类似的方法求解汉诺塔时间复杂度递推式。首先,忽略后面的1,则得到一个齐次线性递推式:
转化为多项式方程:
因为方程是一次多项式,我们直接得到了其解为2。因此齐次递推式的通解为 然后我们需要求得
最后我们求解常数c。 将初始条件
数学原理上面两个例子可能有些同学看的不是很明白,其中提到了一些线性代数术语。在这一章节中,我们分析上述解法的数学原理,看看递推式是如何与线性代数关联起来的。 线性递推式的一般化斐波那契数列和汉诺塔递推式可以看成线性递推式的特例,下面给出线性递推式的一般定义: 我们将满足如下递推关系的递推式称为线性递推式:
其中 注意仅有递推式是不能求得
齐次递推式求解定理下面先考虑齐次线性递推式的求解。定理如下:
定理的证明要证明以上定理,主要需要证明两部分。一是证明多项式根的线性组合可以满足递推式,二是证明任意初始条件下总有解。 可满足性证明首先来证明
任意初始值有解证明下面要证明对于任意初始条件,均存在适当的常数
通用解法通过上面的数学分析,我们得到了一个解线性递推式的通用方法。 齐次递推式设有齐次递推式
我们可以写出其特征多项式方程
解出其k个根
然后将初始条件
解线性方程组得唯一解
非齐次递推式对于非齐次递推式
可以首先按上面的方法求解其齐次部分的通解
然后用同样的方法带入初始值,通过线性方程组求出个常量参数带回即可(具体可参见例2)。 有重根的情况上面的解法只针对特征根互异,如果有重根的话,则上述方法会无效。不过只要经过一定处理也可以有通用方法求解, 因有点复杂,本文不在针对重根情况进行叙述。关于重根情况下的求解,有感兴趣的同学可以参考线性代数或微分方程相关文献。 |
|