递归方程解的渐近阶的求法

word递归方程解的渐近阶的求法递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进展分析的关键步骤。 递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比拟实用的五种方法。 1. 代入法这个方法的根本步骤是先推测递归方程的显式解，然后用数学归纳法证明这一推测的正确性。那么，显式解的渐近阶即为所求。 2. 迭代法  这个方法的根本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。 3. 套用公式法这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况下方程解的渐近阶的三个相应估计公式供套用。 4. 差分方程法  有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问题)的方法来解递归方程。然后对得到的解作渐近阶的估计。 5. 母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的根本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。 本章将逐一地介绍上述五种方法，并分别举例加以说明。 本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。递归方程组解的渐进阶的求法代入法用这个方法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。例如，我们要估计T(n)的上界，T(n)满足递归方程：其中是地板(floors)函数的记号，表示不大于n的最大整数。我们推测T(n)=O(nlog n)，即推测存在正的常数C和自然数n0，使得当nn0时有：T(n)log n (6.2)事实上，取n0=22=4，并取那么，当n0n2n0时，(6.2)成立。今归纳假设当2k-1n0n2kn0 ，k1时，(1.1.16)成立。那么，当2kn0n2k+1n0时，我们有：即(6.2)仍然成立，于是对所有nn0，(6.2)成立。可见我们的推测是正确的。因而得出结论：递归方程(6.1)的解的渐近阶为O(nlogn)。这个方法的局限性在于它只适合容易推测出答案的递归方程或善于进展推测的高手。推测递归方程的正确解，没有一般的方法，得靠经验的积累和洞察力。我们在这里提三点建议：(1) 如果一个递归方程类似于你从前见过的其解的方程，那么推测它有类似的解是合理的。作为例子，考虑递归方程：右边项的变元中加了一个数17，使得方程看起来难于推测。但是它在形式上与(6.1)很类似。实际上，当n充分大时与相差无几。因此可以推测(6.3)与(6.1)有类似的上界T(n)=O(nlogn)。进一步，数学归纳将证明此推测是正确的。(2)从较宽松的界开始推测，逐步逼近准确界。比如对于递归方程(6.1)，要估计其解的渐近下界。由于明显地有T(n)n，我们可以从推测T(n)=(n)开始，发现太松后，把推测的阶往上提，就可以得到T(n)=(nlog n)的准确估计。(3)作变元的替换有时会使一个末知其解的递归方程变成类似于你曾见过的其解的方程，从而使得只要将变换后的方程的正确解的变元作逆变换，便可得到所需要的解。例如考虑递归方程：看起来很复杂，因为右端变元中带根号。但是，如果作变元替换m=logn，即令n=2m，将其代入(6.4)，如此(6.4)变成：把m限制在正偶数集上，如此(6.5)又可改写为：T(2m)=2T(2m/2)+m假如令S(m)=T(2m)，如此S(m)满足的递归方程：S(m)=2S(m/2)+m ，与(6.1)类似，因而有：S(m)=O(m1og m)，进而得到T(n)=T(2m)=S(m)=O(m1ogm)=O(lognloglogn) (6.6)上面的论证只能明确：当(充分大的)n是2的正偶次幂或换句话说是4的正整数次幂时(6.6)才成立。进一步的分析明确(6.6)对所有充分大的正整数n都成立，从而，递归方程(6.4)解的渐近阶得到估计。在使用代入法时，有三点要提醒：(1)记号O不能滥用。比如，在估计(6.1)解的上界时，有人可能会推测T(n)=O(n)，即对于充分大的n，有T(n) ，其中C是确定的正的常数。他进一步运用数学归纳法，推出：从而认为推测T(n)=O(n)是正确的。实际上，这个推测是错误的，原因是他滥用了记号O ，错误地把(C+l)n与等同起来。(2)当对递归方程解的渐近阶的推测无可非议，但用数学归纳法去论证又通不过时，不妨在原有推测的根底上减去一个低阶项再试试。作为一个例子，考虑递归方程其中是天花板(floors)函数的记号。我们推测解的渐近上界为O(n)。我们要设法证明对于适当选择的正常数C和自然数n0，当nn0时有T(n)。把我们的推测代入递归方程，得到：我们不能由此推断T(n)，归纳法碰到障碍。原因在于(6.8)的右端比多出一个低阶常量。为了抵消这一低阶量，我们可在原推测中减去一个待定的低阶量b，即修改原来的推测为T(n)-b 。现在将它代人(6.7)，得到：只要b1，新的推测在归纳法中将得到通过。(3)因为我们要估计的是递归方程解的渐近阶，所以不必要求所作的推测对递归方程的初始条件如T(0)、T(1)成立，而只要对T(n)成立，其中n充分大。比如，我们推测(6.1)的解T(n)logn，而且已被证明是正确的，但是当n=l时，这个推测却不成立，因为(logn)|n=1=0而T(l)>0。递归方程组解的渐进阶的求法迭代法用这个方法估计递归方程解的渐近阶不要求推测解的渐近表达式，但要求较多的代数运算。方法的思想是迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。作为一个例子，考虑递归方程：接连迭代二次可将右端项展开为：由于对地板函数有恒等式：(6.10)式可化简为：这仍然是一个递归方程，右端项还应该继续展开。容易看出，迭代 i 次后，将有6.11而且当时，(6.11)不再是递归方程。这时：(6.13)又因为aa，由(6.13)可得：而由(6.12)，知ilog4n ，从而，代人(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) 。以上两个例子明确，借助于递归树，迭代法变得十分简单易行。递归方程组解的渐进阶的求法套用公式法这个方法为估计形如：T(n)=aT(n/b)+f(n) (6.17)的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a1和b1是常数，f (n)是一个确定的正函数。(6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。这个方法依据的是如下的定理：设a1和b1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是n/b，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式：1. 假如对于某常数>0，有，如此； 2. 假如，如此； 3. 假如对其常数>0，有且对于某常数c>1和所有充分大的正整数n有af(n/b)cf(n)，如此T(n)=(f(n)。 这里省略定理的证明。在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉与的三类情况，都是拿f(n)与作比拟。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数较大，如此T(n)=()；在第三类情况下，函数f(n)较大，如此T(n)=(f (n)；在第二类情况下，两个函数一样大，如此T(n)=()，即以n的对数作为因子乘上f(n)与T(n)的同阶。此外，定理中的一些细节不能无视。在第一类情况下f(n)不仅必须比小，而且必须是多项式地比小，即f(n)必须渐近地小于与的积，是一个正的常数；在第三类情况下f(n)不仅必须比大，而且必须是多项式地比大，还要满足附加的“正规性条件：af(n/b)cf(n)。这个附加的“正规性条件的直观含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数根本上都满足这个正规性条件。还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落在这两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。下面是几个应用例子。例1 考虑T(n)=9T(n/3)+n0对照(6.17)，我们有a=9，b=3， f(n)=n， ，取，便有，