Algorithm 版 (精华区)

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

递归方程组解的渐进阶的求法——迭代法
用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运
算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过
对和式的估计来达到对方程左端即方程的解的估计。
作为一个例子，考虑递归方程：
接连迭代二次可将右端项展开为：
由于对地板函数有恒等式：
(6.10)式可化简为：
这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代 i 次后，将有
 （6.11）
而且当
时，(6.11)不再是递归方程。这时：
 (6.13)
又因为[a]≤a，由(6.13)可得：
而由(6.12)，知i≤log4n ，从而
，
代人(6.14)得：
即方程(6.9)的解  T(n)=O(n)。
从这个例子可见迭代法导致繁杂的代数运算。但认真观察一下，要点在于确定达到初始
条件的迭代次数和抓住每次迭代产生出来的"自由项"(与T无关的项)遵循的规律。顺便指
出，迭代法的前几步迭代的结果常常能启发我们给出递归方程解的渐近阶的正确推测。
这时若换用代入法，将可免去上述繁杂的代数运算。
图6-1 与方程(6.15)相应的递归树
为了使迭代法的步骤直观简明、图表化，我们引入递归树。靠着递归树，人们可以很快
地得到递归方程解的渐近阶。它对描述分治算法的递归方程特别有效。我们以递归方程

T(n)=2T(n/2)+n2 (6.15)
为例加以说明。图6-1展示出(6.15)在迭代过程中递归树的演变。为了方便，我们假设n
恰好是2的幂。在这里，递归树是一棵二叉树，因为(6.15)右端的递归项2T(n/2)可看成
T(n/2)+T(n/2)。图6-1(a)表示T(n)集中在递归树的根处，(b)表示T(n)已按(6.15)展开
。也就是将组成它的自由项n2留在原处，而将2个递归项T(n/2)分别摊给它的2个儿子结
点。(c)表示迭代被执行一次。图6-1(d)展示出迭代的最终结果。
图6-1中的每一棵递归树的所有结点的值之和都等于T(n)。特别，已不含递归项的递归树
(d)中所有结点的值之和亦然。我们的目的是估计这个和T(n)。我们看到有一个表格化的
办法：先按横向求出每层结点的值之和，并记录在各相应层右端顶格处，然后从根到叶
逐层地将顶格处的结果加起来便是我们要求的结果。照此，我们得到(6.15)解的渐近阶
为θ(n2)。
再举一个例子。递归方程：
T(n)= T(n/3)+ T(2n/3)+n (6.16)
的迭代过程相应的递归树如图6-2所示。其中，为了简明，再一次略去地板函数和天花板
函数。
图6-2迭代法解(6.16)的递归树
当我们累计递归树各层的值时，得到每一层的和都等于n，从根到叶的最长路径是
设最长路径的长度为k，则应该有
，
得
，
于是
即T(n)=O(nlogn) 。
以上两个例子表明，借助于递归树，迭代法变得十分简单易行。

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

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