用递推关系理论分析递归算法的时间复杂度.doc
用递推关系理论分析递归算法的时间复杂度 递归算法是算法设计中常用的技术,但对递归算法的时间复杂度分析却是困难的。用组合数学中的递推关系理论可以分析递归算法的时间复杂度。本文提出用递推关系理论分析递归算法的时间复杂度,并推导出三个推论,具有重要的参考价值。 时间复杂度是算法分析与研究的重要内容,通常用重复执行次数最多的语句频度来分析算法的时间复杂度。例如,对n个存放于数组a[n]中的数进行选择法排序的算法,时间复杂度为t(n) = (n2 - n) = O(n2)。然而,对一个算法的时间复杂度并不总是可以轻易地分析出来,特别是对递归算法。 递归算法是程序设计时经常采用的有效手段,如求解n阶hanoi塔问题的递归算法。然而,遇到递归算法时,无法轻易地分析出其时间复杂度。为了解决这个问题,可以利用组合数学中的母函数与递推关系理论来分析递归算法的时间复杂度。 递推关系理论是组合数学中的一个重要概念,用于分析递归序列的时间复杂度。k阶常系数线性递推关系式是指an + C1an-1 + C2an-2 + ... + Ckan-k = 0,where C1, C2, ..., Ck是常数。对应于k阶常系数线性递推关系的多项式C(x) = xk + C1xk-1 + ... + Ck称为序列{an}的特征多项式。 根据递推关系理论,可以推导出三个推论: 推论1:设某一递归算法时间复杂度函数为t(n),如果其k阶常系数递推关系式所对应的特征多项式C(x)有k个不同的根β1, β2, ..., βk,则t(n)的解为t(n) = A1β1n + A2β2n ... + Akβkn,其中A1, A2, ..., Ak为k个待定常数。 例如,对n阶hanoi塔问题的递归算法进行分析。不妨设h(n)表示将n个盘子从one座移动到three座所需的转移次数亦即hanoi问题算法的时间复杂度。根据算法先把前面n-1个盘子转移到two座上(移动次数为h(n-1)次),然后把第n个盘子转移到three座上(移动次数为1次);最后再一次将two座上的n-1个盘子转移到three座上(移动次数为h(n-1)次)。则显然有h(n) = 2h(n-1) + 1,h(1) = 1同样有h(n-1) = 2h(n-2) + 1。则可以得到2阶(即k = 2)常系数线性递推关系式h(n) - 3h(n-1) + 2h(n-2) = 0根据递推关系理论,序列h(n)所对应的特征多项式为x2 - 3x + 2 = (x - 1)(x - 2),则h(n) = A1*1n + A2*2n其中A1和A2为待定常数。