递归式 | 查问题
汇聚最新编程技术，编程问题一网打尽
[ 分类： ]
　　当一个算法包含对自身的递归调用时，其运行时间通常可以用递归式来表示。递归式是一组等式或不等式，它所描述的函数是用在更小的输入下该函数的值来定义的，如
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　T(n)=&T(1) & & & & &　　　如果n=1
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　T(n)=2T(n/2)+&T(n)　　如果n&1
其解为T(n)=&(nlgn)。本篇文章介绍了三种解递归式的方法，即找出解的渐近&T或O界的方法。在代换法中，我们先猜有某个界存在，然后再用数学归纳法证明该猜测的正确性。递归树方法将递归式转换成树形结构，树中的节点代表在不同递归层次付出的代价。最后，再利用对和式限界的技术来解出递归式。主方法给出递归形式T(n)=aT(n/b)+f(n)的界，其中a&1,b&1，f(n)是给定的函数；这种方法要记忆三种情况，但一旦做到了这点，确定很多简单递归式的界就很容易了。
　　在实践中，在表达和解递归式时常常略去一些技术性细节。首先，常常假设函数的自变量为整数；对于固定规模的输入来说，算法的运行时间为常量，股对于足够小的n来说，表示算法运行时间的递归式一般为T(n)=&T(1)；在表示并解递归式时，常忽略上取整和下取整以及边界条件，进行分析是先假设没有这些细节，而后再确定他们是否重要。他们通常不重要，但是重要的是要知道他们在什么情况下是事关紧要的。经验以及已知的一些定理告诉我们：这些细节不会影响算法分析中遇到的许多递归式渐近界。然而，本篇文章中，我们将讨论一些细节，以展示递归式揭发的微妙之处。
　　用代换法解递归式需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。代换法这一名称源于当归纳假设用较小的值时，用所猜测的值代替函数的解。这种方法很有效，但是只能用于界的形式很容易猜的情形。如
　　　　　　　　　　　　T(n)=2T(&n/2&)+n
首先猜测其解为T(n)=O(nlgn)。我们的方法是证明T(n)&cnlgn，其中c&0是某个常数。先假设这个界对&n/2&成立，即T(&n/2&)&c&n/2&lg(&n/2&)。对递归式做替换，有　　 &　　　　　 & 　　　　　　　　　　T(n)&2(c&n/2&lg(&n/2&))+n&cnlg(n/2)+n=cnlgn-cnlg2+n=cnlgn-cn+n&cnlgn
其中最后一步，只要c&1就成立。接下来应用数学归纳法就要求解对边界条件成立。一般来说，可以通过证明边界条件符合归纳证明的基本情况来说明他的正确性。一般来说，可以通过证明边界条件符合归纳证明的基本情况来说明它的正确性。但是这些要求有时会导致问题，假设T(1)=1是递归式唯一的边界条件，那么对于n=1时，T(n)&cnlgn也就是T(1)&clg1=0，与T(1)=1不相符。因此，归纳证明的基本情况能满足。
　　对特殊边界条件证明归纳假设中的这种困难很容易解决。对式子T(n)=2T(&n/2&)+n，利用渐进记号，只要求对n&n0，证明T(n)&cnlgn，其中n0是常数。这样做的思想是在归纳证明中，对困难的边界条件T(1)=1不加以考虑。我们可以把T(2)T(3)作为归纳证明中的边界条件代替T(1)，让n0=2，这时因为对n&3，递归不直接依赖与T(1)。这样我们就把递归式的基本情况和n=1和归纳证明的基本情况n=2和n=3区分开了。通过递归可以求出T(2)=4和T(3)=5。归纳证明T(n)&cnlgn正确性时，其中常量c&1，只要c取足够大的常数使得T(2)&2clg2和T(3)&3clg3即可完成证明。
　　做一个好的猜测：不幸的是，并不存在通用的方法来猜测递归式的正解。第一种方法是根据经验进行猜测；第二种是先证明递归式的教松的上下界，然后在缩小不确定性区间
　　一些细微的问题：有时，我们或许能够猜出递归式的渐近界，但却会在归纳证明时出现一些问题。通常，问题处在归纳假设不够强，无法证明其准确的界。遇到这种情况，可以去掉一个低阶项来修改所猜的界，使得证明顺利进行。考虑下面的递归式：
　　　　　　　　　　　　T(n)=T(&n/2&)+T(&n/2&)+1
我们猜测其解为O(n)，即要证明对适当选择的c，有T(n)&cn。用所猜测的界对递归式做替换，有
　　　　　　　　　　　　T(n)&c&n/2&+c&n/2&+1=cn+1
由此引不出T(n)&cn，因为无论c为何值，读者可能会猜到一个更大的界，如T(n)=O(n2)，虽然这确实是上界，但事实上，我们所猜测的解T(n)=O(n)是正确的，为了证明这一点，要做一个更强的归纳假设。从直觉上来说，我们的猜测几乎是正确的，只是差了一个常数1，即一个低阶项。然而，就因为差了一项，数学归纳法就无法证明期望的结果。从所作的猜测中减去一个低阶项，即T(n)&cn-b,b&0是个常数，现在有
　　　　　　　　　　　　T(n)&c&n/2&-b+c&n/2&-b+1=cn-2b+1=cn-2b+1&cn-b
只要b&1，像以前一样，c要选择的足够大，一边能够处理边界条件。为什么不是增加一项来解决问题呢？关键在于要理解我们是在用数学归纳法：通过对更小的值做更强的假设，就可以证明对某个给定值的更强的结论
　　避免陷阱：在运用渐近表示时很容易出错，例如在式子T(n)=2T(&n/2&)+n中，有假设T(n)&cn并证明
　　　　　　　　　　　　T(n)&2(c&n/2&)+n&cn+n=O(n)
因为c是常数，因而错误的证明了T(n)=O(n)。错误在于没有证明归纳假设的准确性是，即T(n)&cn
　　改变变量：有时候对一个陌生的递归式做一些简单的代数变换，就会使之变成读者较为熟悉的形式。考虑
　　　　　　　　　　　　T(n)=2T(&&n&)+lgn
这个式子看起来比较难，但是可以进行简化，方法是改动变量。为了方便起见，不考虑数的街区整数问题，如将&n华为整数。设m=lgn，有
　　　　　　　　　　　　T(2m)=2T(2m/2)+m
再设S(m)=T(2m)，得到新的递归式
　　　　　　　　　　　　S(m)=2S(m/2)+m
这个式子看来就非常熟悉了，这个新的递归式的边界是：S(m)=O(mlgm)。将S(m)代回T(n)，有T(n)=T(2m)=S(m)=O(mlgm)=O(lgnlglgn)。
递归树方法
　　画出递归树是一种得到好猜测的直接方法。在递归树中，每一个节点都代表递归函数调用集合中一个子问题的代价。我们将树中的每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归是所有层次的总代价。当用递归式表示分治算法的运行时间时，递归树的方法有其有用。递归树适合用来产生好的猜测，然后用代换法加以验证。但使用递归树产生好的猜测时，通常可以容忍销量的不良量，因为稍后就会证明所咋uodcaice。如果画递归树时非常地仔细，并且将代价都嫁了起来，那么就可以直接用递归树作为递归式解的证明。来看递归树如何为递归式T(n)=3T(&n/4&)+&T(n2)提供良好的猜测。一开始我们先解决找到上界的问题。因为知道底和顶函数在解决递归式问题式并不重要，所以建立了一个关于递归式T(n)=3T(&n/4&)+cn2的递归树，常系数c&0。
　　下面演示了递归树的演化过程，为了方便，不妨设n是4的幂。先显示了T(n)，然后将其扩展成一个等价的用来表示递归的书。根部的cn2项表示递归在顶层时所花的代价，而根部一下的三颗子树表示这些n/4大小的子问题所需的代价，最后再将其扩展：
&　　　　　　　　　　　　　　　　cn2　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cn2　　
　　　　　　　　　　T(n/4)　　T(n/4)　　T(n/4)　　　　　　　　　　　　c(n/4)2　　　　　　　　　　　　c(n/4)2　　　　　　　　　　　　c(n/4)2
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　T(n/16)&T(n/16)&T(n/16) 　　　&T(n/16)&T(n/16)&T(n/16) 　　　&T(n/16)&T(n/16)&T(n/16)
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cn2　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 &&&cn2
　　　　　　　　　　　　　　　　　　　c(n/4)2　　　　　　　　　　　　c(n/4)2　　　　　　　　　　　　c(n/4)2　　　　　　　　　　　　　　　　　　　　 &&(3/16)cn2
　　　　　　　　　　　　　　c(n/16)2c(n/16)2c(n/16)2　　c(n/16)2c(n/16)2c(n/16)2　　c(n/16)2c(n/16)2c(n/16)2&　　　　　　　　　　　　&(3/16)2cn2
　　　　　　　　　　　……………………………………………………………………………………………………………………..
log4n行　　　　　T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)T(1)………………………….T(1)T(1)T(1)T(1)T(1)T(1)　　　　　　 & &&&&T(nlog43)
　　下面将所有层次的代价相加得到整棵树的代价
　　　　　　　　　　　　　　T(n)=cn2+(3/16)cn2+(3/16)2cn2+…+(3/16)log4n-1cn2+&T(nlog43)=[([3/16]log4n)-1]cn2/[(3/16)-1]+&T(nlog43)&cn2/[1-(3/16)]+&T(nlog43)=(16/13)cn2+&T(nlog43)=O(n2)
于是，我们得到了原来的递归式T(n)=3T(&n/4&)+&T(n2)的一个猜测。事实上，如果O(n2)确实是此递归式的上界，那么它一定是确界，为什么呢？因为第一个递归调用需要的代价是&T(n2)，所以&T(n2)一定是此递归式的下界。现在我们使用代换法来验证猜测的正确性，T(n)=O(n2)是递归式T(n)=3T(&n/4&)+&T(n2)的一个上界。我们需要证明，当某常数d&0,T(n)&dn2成立。适用与前面相同的常数c&0，有
　　　　　　　　　　　　　　T(n)&3T(&n/4&)+cn2&3d(&n/4&)2+cn2&3d(n/4)2+cn2=(3/16)dn2+cn2&dn2
只要d&16c/13，最后一步都会成立。
　　现在来看另外一个较为复杂的例子，递归树
　　　　　　　　　　　　　　T(n)=T(n/3)+T(2n/3)+O(n)
与前面一样，我们使用c来代表O(n)项的常数引资，当将递归树内各层加起来时，可以得到每一层的cn的值。从根部到叶子的最长路径是n,2n/3,(2/3)2n…1。因为当k=log3/2n时，(2/3)kn=1，所以树的深度是log2/3n:
　　　　　　　　　　　　　　　　　　　　　　　　　　cn　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cn
　　　　　　　　　　　　　　　　　　 & &c(n/3)　　　　　　　　c(2n/3)　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cn
　　　　　　　　　　　　　　　　c(n/9)　　c(n/9)　　　　c(2n/9)　　c(2n/9)　　　　　　　　　　　　　　　　　　　　　　　　　　　 &cn
log3/2n层　　　　　　　　　　………………………………………………………….　　　　　　　　　　　　　　　　　　　　　　　　　　 &cn
直觉上，我们预期递归式的解为O(cnlog3/2n)=O(nlgn)。这里还有一个复杂点，我们还没有考虑叶子的代价。如果这棵树是高度为log2/3n的完整二叉树，那么有2log3/2n=nlog3/22，个叶子节点，由于叶子的代价是常数，因此所有叶子代价的综合为&T(nlog3/22)，然而这颗递归树并不是完整的二叉树，少于nlog3/22个叶子，而且从树根往下的过程中，悦来越多的内部节点在小时。因此，并不是所有层次都刚好需要cn代价；越靠近底层，需要的代价越少。我们可以计算出准确的总代价，但记住我们只是想要找出一个猜测来使用到代换法中。然我们容忍这些误差，来证明上界为O(nlgn)的猜测时正确的
　　下面证明T(n)&dnlgn，当d是一个合适的正值常数，有
　　　　　　　　　　　　T(n)&T(n/3)+T(2n/3)+cn
　　　　　　　　　　　　　　&d(n/3)lg(n/3)+d(2n/3)lg(2n/3)+cn
& & & & & & & & & & & & & & & & & & & &=(d(n/3)lgn-d(n/3)lg3)+(d(2n/3)lgn-d(2n/3)lg(3/2))+cn
　　　　　　　　　　　　　　=dnlgn-d((n/3)lg3+(2n/3)lg(3/2))+cn
　　　　　　　　　　　　　　=dnlgn-d((n/3)lg3+(2n/3)lg3-(2n/3)lg2)+cn
　　　　　　　　　　　　　　=dnlgn-dn(lg3-2/3)&dnlgn
上式成立的条件是d&c/(lg3-(2/3))。因此，没有必要去更准确地计算递归树中的代价
　　主方法给出求解如下形式的递归式的方法：
　　　　　　　　　　　　　　　　　　　　T(n)=aT(n/b)+f(n)
其中a&1和b&1是常数，f(n)是一个渐近正的函数。主方法要求记忆三种情况，但这样可很容易确定许多递归式的解，且不需用笔和纸。从技术正确性角度看，递归式实际上没有得到很好的定义，因为n/不可能不是个整数。但是用T&n/b&或者T&n/b&来代替a项T(n/b)并不影响递归式的渐近行为。因而我们在写分支算法时略去下取整和上取整函数会带来很大的方便。
　　主定理：设a&1和b&1为常数，设f(n)为一函数，T(n)由递归式T(n)=aT(n/b)+f(n)对非负整数定义，其中n/b指&n/b&或者&n/b&。那么T(n)可能有如下的渐近界：
　　　　　　　　若对于某常数&&0，有f(n)=O(nlogba-e)，则T(n)=&T(nlogba)
　　　　　　　　 & &若f(n)=&T(nlogba)，则T(n)=&T(nlogbalgn)
　　　　　　　　若对某常数&&0，有f(n)=&O(nlogba+e)，且对常数c&1与所有足够大的n，有af(n/b)&cf(n)，则T(n)=&T(f(n))
　　在以上三种情况的每一种中，都把函数f(n)与函数nlogba比较。第一种情况中，函数nlogba较大，则解为T(n)=&T(nlogba)；第三种情况下，f(n)是较大的函数，则解为T(n)=&T(f(n))；在第二种情况中，两种函数同样大，乘以对数引资，则解为T(n)=&T(nlogbalgn)。要注意三种情况并没有覆盖所有可能的f(n)。当f(n)只是小于nlogba但不是多项式地小于时，在第一种情况和第二种情况之间就存在一条沟。类似情况下，当f(n)大于nlogba但多项式地打，第二种情况和第三种情况之间就会存在一条沟。如果f(n)落在任一条沟中，或是第三种情况中规则性条件不成立，则主方法就不能用于解递归式。
　　先看第一个例子：T(n)=9T(n/3)+n，在这个递归式中a=9，b=3，f(n)=n，则nlogba=nlog39=&T(n2)。因为f(n)=O(nlog39-&)，其中&=1，这对应主定理中的第一种情况，所以答案为T(n)=&T(n2)
　　第二个例子T(n)=T(2n/3)+1中，a=1，b=3/2，f(n)=1，nlogba=nlog3/21=n0=1。第二种情况成立，因为f(n)=&T(nlogba)=&T(1)，故递归式的解为T(n)=&T(lgn)
　　再看一个例子：T(n)=3T(n/4)+nlgn，有a=3，b=4，f(n)=nlgn，nlogba=nlog43=&T(n0.793)。因为f(n)=&O(nlog43+&)，其中&&0.2，如果能证明对f(n)第三种情况中的规则性条件成立，则选用定理中的第三种情况。对足够大的n，af(n/b)=3(n/4)lg(n/4)&(3/4)nlgn=cf(n)，c=3/4，则递归式的解为T(n)=&T(nlgn)
　　但是对于下面的这个递归式：T(n)=2T(n/2)+nlgn，这个递归式在形式上是合适的，a=2，b=2，f(n)=nlgn，nlogba=n，看上去可以选择第三种情况，因为f(n)=nlgn渐近大于nlogba=n，但并不是多项式大于。对任意正常数&，比值f(n)/nlogba=(nlgn)/n=lgn，渐近小于n&。因此，该递归式落在情况二与三之间。
　　　　　　　　　　　　　　　　　　　　算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法
算法设计关于递归方程T(n)=aT(n/b)+f(n)之通用解法
在算法设计中经常需要通过递归方程估计算法的时间复杂度T(n)，本文针对形如T(n)=aT(n/b)+f(n)的递归方程进行讨论，以期望找出通用的递归方程的求解方式。
算法设计教材中给出的Master定理可以解决该类方程的绝大多数情况，根据Master定理：o-渐进上界、w-渐进下界、O-渐进确界。
设a≥1，b＞1为常数，f(n)为函数，T(n)=aT(n/b)+f(n)为非负数,令x=logba：
f(n)=o(nx-e)，e＞0，那么T(n)=O(nx)。
f(n)=O(nx)，那么T(n)=O(nx
f(n)=w(nx+e)，e＞0且对于某个常数c＜1和所有充分大的n有af(n/b)≤cf(n)，那么T(n)=O(f(n))。
然而，Master定理并没有完全包括所有的f(n)的情况。注意到条件1和3中的e总是大于0的，所以在条件1和2、条件2和3之间存在所谓的“间隙”，使得某些f(n)在该情况下不能使用该定理。因此，我们需要找到在Master定理不能使用的情况下如何解递归方程的比较通用的办法——递归树。
经过分析，递归树解法包含了Master定理，但是Master定理可以方便的判断出递归方程的解。产生这种结果的原因关键在于f(n)的形式，显然，当f(n)是n的多项式p(n)形式的话必然满足Master定理的要求，但是f(n)不是多项式就需要另当别论了。
下面就题目所列出的递归方程形式进行分析。
一、f(n)是n的多项式p(n)=f(n)
因为f(n)是多项式，设p(n)=O(nk)，k≥0。根据递归树计算方式，有：
T(n)= aT(n/b)+nk 。
aT(n/b2)+(n/b)k 。
aT(n/b3)+( n/b2)k 。
于是得到：T(n)= nk (1+ a/
bk + (a/ bk)2 + (a/
bk)3 +···+ (a/
bk)h)，h=logbn。
1：logba=k
这种情况下a/ bk= 1，显然T(n)=
O(nk logbn)。
2：logba≠k
此时等比数列公比不是1，根据等比数列求和公式化简得到：
&nx)/(1-a/bk)，x=logba。
如果logba&k，则T(n)=
如果logba&k，则T(n)=
O(nx)。x=logba。
通过以上的计算表明，在Master定理的条件中，针对f(n)为多项式的情况可以使用递归树的方法进行证明和计算。同样，在f(n)不是多项式的时候也可以通过的这种方式得到方程的解。
二、f(n)是一般函数
当f(n)不是n的多项式的时候，计算就会变得比较复杂，有时可能会也找不到最终的解。但是递归树的方法给我们一种更好使用的解决办法。下面根据一个简单的例子说明这一点：
当a=b=2、f(n)=nlgn时候（lgn:log2n的简记），计算递归方程的解。
T(n)= 2T(n/2)+nlgn 。
2T(n/22)+(n/2)lg(n/2)。
2T(n/23)+ (n/22)lg(n/22)。
于是得到：T(n)= nlgn+(nlgn-lg2)+
(nlgn-2lg2)+
(nlgn-22lg2)+···+(nlgn-2hlg2)，h=lgn。
根据等差、等比数列求和公式化简有：
T(n)=n(lgn)2
&(n-1)lg2，所以T(n)= O( n(lgn)2)，而不是O(
通过这个例子可以看出，当f(n)不是多项式的时候计算就有可能变得比较复杂，甚至无法计算。但是通过递归树以及具体的数学变换技巧在某些情况下还是可行的。
综上所述，可以得出以下结论：在针对形如T(n)=aT(n/b)+f(n)的递归方程求解方法里，使用递归树是一种比较可行的通用办法。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。你的浏览器禁用了JavaScript, 请开启后刷新浏览器获得更好的体验!
T(N)=2T(N/2)+logN
$$T(N) = aT(\frac{N}{b}) + f(N)$$
这种递归式的复杂度都是这样求解，首先
$$T(N) = aT(\frac{N}{b}) + f(N)$$
$$ = a^2 T(\frac{N}{b^2}) + af(\frac{N}{b}) + f(N)$$
$$\vdots$$
$$=a^{log_b N}T(1) + a^{log_b N-1}f\bigg(\frac{N}{b^{log_b N-1}}\bigg) + \cdots + af\bigg(\frac{n}{b}\bigg) + f(n)$$
$$=N^{log_b a}T(1) + \sum\limits_{i=0}^{log_b N-1} a^i f\bigg(\frac{N}{b^j}\bigg)$$
$$=\Theta(n^{log_b a}) + \sum\limits_{i=0}^{log_b N-1} a^i f(\frac{N}{b^j})$$
然后你就需要比较这两项谁更大，只给结论
$$f(N) & \Theta(n^{log_b a})$$
则总的复杂度为
$$T(N) = \Theta(n^{log_b a})$$
$$f(N) > \Theta(n^{log_b a})$$
则总的复杂度为
$$T(N) = \Theta(f(N))$$
$$f(N) = \Theta(n^{log_b a})$$
则总的复杂度为
$$T(N) = \Theta(N^{log_b a}log_bN)$$
至于为什么，随便找本算法书来看吧，基本都会涉及这块内容
而你的问题，套公式就能得到答案：D
要回复问题请先或
可以subString、subArray、subSequence为什么不可以subVoid
关注: 3 人}