3递推递归的复杂性分析课件.ppt

1、2022-12-20计算计算法设计与分析12.3 递推递归的复杂性分析2022-12-20计算计算法设计与分析2递归复杂性的一般形式 一般的，递归关系描述为递归方程：1 n=1 aT(n b)+D(n)n1T(n)=其中，a是子问题个数，b是递减步长，表示递减方式，D(n)是合成子问题的开销。通常，递归元的递减方式有两种：1、除法，即n/b，的形式；2、减法，即n b，的形式。分治分治递推递推2022-12-20计算计算法设计与分析3递推关系与递归 算术序列：h0,h0+q,h0+2q,h0+nq,.或为递归式：h(n)=h(n 1)+q，h(0)=h0。几何序列：h0,qh0,q2h0,qn

2、h0,.或为递归式：h(n)=qh(n1)，h(0)=h0。如果递归式的递减方式是减法的话，则递归式按其递归元就形成一个递推序列。2022-12-20计算计算法设计与分析4递推递归的时间复杂性 k1 i=0=akT(1)+ai D(n ib)这里k=n/b。不失一般性令b=1，则k=n。若设D(n)为常数，则有T(n)=O(an)。若为减法，即n b，则有：T(n)=aT(n b)+D(n)=a(aT(n 2b)+D(n b)+D(n)=k1 i=0=ak+ai D(n ib)在通常的情况下递推在通常的情况下递推递归的时间复杂性为递归的时间复杂性为指数函数。指数函数。2022-12-20计算计

3、算法设计与分析5n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？所谓相互交叠的圆是指两个圆相交所谓相互交叠的圆是指两个圆相交在不同的两点。在不同的两点。2022-12-20计算计算法设计与分析6n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？令h(n)为平面上有n个互相交叠的圆所形成的区域数。h(n)=?让我们先从最简单的情况来考虑。2022-12-20计算计算法设计与分析7n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？令h(n)为平面上有n个互相交叠的圆所形成的区域数。显然h(0)=1。h

4、(1)=2。h(2)=4。h(3)=8。h(4)=？h(4)=142022-12-20计算计算法设计与分析8n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？令h(n)为平面上有n个互相交叠的圆所形成的区域数。h(n)=?我们仍然不知道。我们该怎么做呢？我们该怎么做呢？2022-12-20计算计算法设计与分析9n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？令h(n)为平面上有n个互相交叠的圆所形成的区域数。这时要考虑复杂情况与较简单情况之间关系，即复杂情况是怎样由较简单情况构成的。2022-12-20计算计算法设计与分析10n

5、个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？假设前面n 1个圆形成h(n1)个区域。现放进第n个圆与前n1个圆交叠。让我们来考虑把这第让我们来考虑把这第n n个圆交个圆交叠上去会造成区域数发生什么叠上去会造成区域数发生什么样的变化呢？样的变化呢？2022-12-20计算计算法设计与分析11n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？假设前面n 1个圆形成h(n1)个区域。现放进第n个圆与前n1个圆交叠。第n个圆与前n1个圆都相交于两点，于是有2(n1)个交点。这2(n1)个点将第n个圆分成2(n1)条弧，而每条弧又将某个

6、区域一分为二，因此新增加的区域数应为2(n1)。2022-12-20计算计算法设计与分析12n个互相交叠的圆的区域数 在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？令h(n)为平面上有n个互相交叠的圆所形成的区域数。于是便得到如下的递归式：h(n)=h(n1)+2(n1)。这个递推递归式有一个简单的通项公式：h(n)=h(n1)+2(n1)。h(n2)+2(n2)+2(n1)h(n3)+2(n3)+2(n2)+2(n1)h(1)+2(1)+2(2)+2(n1)2+2n(n1)/2=n2 n+2。注意此公注意此公式对式对h(0)不成立！不成立！n 0。2022-12-20计算计算法设计

7、与分析13棋盘覆盖问题 一个2k2k特殊棋盘是其中含有一个特殊方格的棋盘，左下图为k=2的一个特殊棋盘。现在任给定一个2k2k特殊棋盘，要用右下图所示的L型骨牌来无重叠的覆盖它。111222333444555在2k2k的棋盘覆盖中要用到(4k1)/3个L型骨牌。2022-12-20计算计算法设计与分析14棋盘覆盖问题 让我们先来考虑最简单的情况：什么是最简单的情况？什么是最简单的情况？最简单情况是k=0。这时棋盘有2020=1个格子，即只有一个特殊格子。这时棋盘已被完全覆盖，无须再做什么了。下面我们来考虑复杂情况是怎样由较简单情况构成的。2022-12-20计算计算法设计与分析15棋盘覆盖问题

8、的分析 当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1 特殊方格必定位于4个子棋盘之一中。而这四个子棋盘却不一致。递归求解是将问题归结到较小规模的同一问题，这就需要将三个正常子棋盘也转化成特殊棋盘。2022-12-20计算计算法设计与分析16棋盘覆盖问题的分析 当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：2k12k12k12k12k12k12k12k1 特殊方格必定位于4个子棋盘之一中。为此，可用一个L型骨牌覆盖三个正常子棋盘的会合处，如左图所示。这次覆盖后四个子棋盘都是特殊棋盘了。2022-12

9、-20计算计算法设计与分析17棋盘覆盖的算法 棋盘覆盖(参数表)如果是单个格子，则返回；将棋盘划分成尺寸为一半的子棋盘；判断特殊方格在哪个子棋盘中，再用相应L型骨牌覆盖相应结合部，即不含特殊方格的部分在结合部的三个方格；并记下它们的位置，作为各部分的特殊方格；依次对左上角、右上角、右下角和左下角四个子棋盘进行棋盘覆盖；2022-12-20计算计算法设计与分析18棋盘覆盖算法中的参数 算法的形参表中需要的参数有：递归元：棋盘尺寸为2n。每轮递归时将n减 1，则棋盘尺寸减半；当n为0时递归终止。棋盘位置：棋盘左上角方格的行列号tr和tc。特殊方格位置：特殊方格的行列号dr和dc。参数表中应有哪些参

10、数呢？参数表中应有哪些参数呢？递归元定义为int n 棋盘位置定义为int tr,tc。特殊方格位置定义为int dr,dc。2022-12-20计算计算法设计与分析19棋盘覆盖算法中其它变量 除了形参表中的那些参数外，棋盘覆盖程序中还需要如下的变量：表示棋盘的变量。表示L型骨牌覆盖顺序的变量。棋盘尺寸的变量。各子棋盘在结合部的方格位置。各子棋盘的特殊方格的位置。除形参外，算法中还应除形参外，算法中还应有哪些变量呢？有哪些变量呢？内部变量全局变量为什么要设这为什么要设这个变量呢？个变量呢？2022-12-20计算计算法设计与分析20棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，

11、初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。不设此变量也可以。但因不设此变量也可以。但因s=2n，则每轮递，则每轮递归中都要做求归中都要做求2n的幂运算。设变量的幂运算。设变量s后，只后，只需初始时计算一次需初始时计算一次s=2n，以后只要做，以后只要做s=s/2即可。这样降低了递归中的运算强度。即可。这样降低了递归中的运算强度。2022-12-20计算计算法设计与分析21棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为

12、2n。0132四个子棋盘的排序为四个子棋盘的排序为 结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。2022-12-20计算计算法设计与分析22棋盘覆盖算法中其它变量 棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s。结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。将棋盘覆盖程序取名为CoverBoard；2022-12-20计算计算法设计与分析23棋盘覆盖的算法 voice CoverBoard(n,tr,tc

13、,dr,dc)if(n=0)return;n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)若只有一个若只有一个格子，则终格子，则终止递归。止递归。注意递归元的递减是注意递归元的递减是在这里做的。在这里做的。s s是减半是减半后的子棋盘尺寸。后的子棋盘尺寸。在对结合部覆盖之前在对结合部覆盖之前将覆盖序号将覆盖序号tiletile加一。加一。2022-12-

14、20计算计算法设计与分析24棋盘覆盖的算法 voice CoverBoard(n,tr,tc,dr,dc)if(n=0)return();n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)Coverjoin完成以下功能：完成以下功能：1、计算结合部的方格的、计算结合部的方格的位置；位置；2、判断特殊方格位置；、判断特殊方格位置；3、覆盖子棋盘结合部并、覆盖

15、子棋盘结合部并将四个特殊方格的位置写将四个特殊方格的位置写入入sr 和和sc。依次对四个子棋依次对四个子棋盘进行覆盖。盘进行覆盖。覆盖左上角覆盖左上角的子棋盘。的子棋盘。覆盖右上角覆盖右上角的子棋盘。的子棋盘。覆盖右下角覆盖右下角的子棋盘。的子棋盘。覆盖左下角覆盖左下角的子棋盘。的子棋盘。2022-12-20计算计算法设计与分析25棋盘覆盖的算法 voice CoverBoard(n,tr,tc,dr,dc)if(n=0)return();n=n 1;s=s/2;tile+;Coverjoin;CoverBoard(n,tr,tc,sr0,sc0);CoverBoard(n,tr+s,tc,s

16、r1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3)依次对四个子棋依次对四个子棋盘进行覆盖。盘进行覆盖。覆盖左上角覆盖左上角的的0号子棋盘。号子棋盘。覆盖右上角覆盖右上角的的1 1号子棋盘。号子棋盘。覆盖右下角覆盖右下角的的2 2号子棋盘。号子棋盘。覆盖左下角覆盖左下角的的3 3号子棋盘。号子棋盘。2022-12-20计算计算法设计与分析26Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。2022-12-20计算计算法设计与分析27C

17、overjoin的实现 计算结合部方格位置：tr是0区和1区的首行，tc是0区和3区的首列;tr+s是3区和2区的首行;tc+s是1区和2区的首列0312trtcss2022-12-20计算计算法设计与分析28Coverjoin的实现 计算结合部方格位置：0312trtcss jr0=tr+s1;jc0=tc+s1;jr1=tr+s1;jc1=tc+s;jr2=tr+s;jc2=tc+s;jr3=tr+s;jc3=tc+s1;jr0=tr+s1;jc0=tc+s1jr1=tr+s1;jc1=tc+sjr2=tr+s;jc2=tc+sjr3=tr+s;jc3=tc+s12022-12-20计算计

18、算法设计与分析29Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：我们可以依据结合部方格的行号和列号来判断特殊方格落在哪个子棋盘中。0132trtcss jr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;2022-12-20计算计算法设计与分析30Coverjoin的实现 计算结合部方格位置：判断特殊方格(dr,dc)落在那个子棋盘：覆盖结合部并确定各子棋盘特殊方格位置。if(dr=jr0&dc=jc0)r=0 else if(dr=jc1)r=1 el

19、se if(dr=jr2&dc=jc2)r=2 else if(dr=jr3&dc=jc3)r=3;jr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;若特殊方格的行标若特殊方格的行标dr=jr0且列标且列标dc=jc0，则特殊，则特殊方格位于在方格位于在0号子棋盘中。号子棋盘中。其余类似。其余类似。r指明了这点。指明了这点。2022-12-20计算计算法设计与分析31Coverjoin的实现 覆盖结合部并确定各子棋盘特殊方格位置：if(r=0)sr0=dr;sc0=dc;Boardjrkjck

20、=tile;srk=jrk;sck=jck;k=1,2,3 else if(r=1)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,2,3 else if(r=2)sr2=dr;sc2=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,3 else if(r=3)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,2;注意：此处由于幻灯片篇幅的原因，简写注意：此处由于幻灯片篇幅的原因，简写成这样，实际表示对于成这样，实际表示对于k=1,2,3，执行，执行

21、Boardjrkjck=tile;srk=jrk;sck=jck;，即覆盖相应格子，并将其即覆盖相应格子，并将其作为对应子棋盘的特殊方格。下面亦如此。作为对应子棋盘的特殊方格。下面亦如此。2022-12-20计算计算法设计与分析32Coverjoin的实现 覆盖结合部并确定各子棋盘特殊方格位置也可以用如下的语句来实现：srr=dr;scr=dc;for(k=0,k 4,i+)if(kr)Boardjrkjck=tile;srk=jrk;sck=jck;特殊子棋盘的特殊方特殊子棋盘的特殊方格还是原来的。格还是原来的。对每个非特殊子棋盘，则覆盖其结合部的方对每个非特殊子棋盘，则覆盖其结合部的方格并

22、将其作为该子棋盘的特殊方格。格并将其作为该子棋盘的特殊方格。由于这个操作可以用此简单表示，所以才在由于这个操作可以用此简单表示，所以才在上一张幻灯片上采用了简记的方式。上一张幻灯片上采用了简记的方式。2022-12-20计算计算法设计与分析33棋盘覆盖算法的主程序 main(int n,int dr,int dc)int s=2n int Boardss=0;int tile=0;CoverBoard(n,0,0,dr,dc);请同学们自己编程来请同学们自己编程来具体实现这个程序。具体实现这个程序。2022-12-20计算计算法设计与分析34棋盘覆盖算法的正确性 要证明一个算法的正确性，需要证

23、明两点：(1)算法的部分正确性；(2)算法的终止性。下面我们用归纳法证明棋盘覆盖算法的部分正确性：2022-12-20计算计算法设计与分析35棋盘覆盖算法的部分正确性 归纳基础：k=0时，特殊棋盘仅含一个特殊方格，显然已经正确覆盖。假设对2k1的特殊棋盘均可正确覆盖。对2k的特殊棋盘，算法划分为四个2k1的子棋盘。用一块L型骨牌覆盖三个正常子棋盘的结合处后，恰形成四个2k1的特殊棋盘。由归纳假设，它们均可被正确覆盖。因而也正确覆盖了2k的特殊棋盘。由归纳法可知，棋盘覆盖算法是部分正确。2022-12-20计算计算法设计与分析36棋盘覆盖算法的终止性 算法的终止性：递归终止条件为递归元size为

24、1时递归终止。递归元size的初值为2k。每次递归时递归元减半，即size=size/2；因此，必然在有穷步内递减为1。所以此算法必定终止。由部分正确性和终止性可知，此算法是完全正确的。2022-12-20计算计算法设计与分析37棋盘覆盖算法的复杂性 设T(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则T(k)满足如下递归方程：T(k)=O(1)k=04T(k1)+O(1)k0 递归元递减方式是减法，故此分治法实质是递推关系。由a=4可知T(k)=O(4k)。覆盖2k2k的棋盘要用(4k1)/3个L型骨牌，故此算法是一个在渐进意义下最优的算法。2022-12-20计算计算法设计与分析38

25、小结 用减法方式递减的递归式按其递归元形成一个递推序列。递推关系的递归程序的时间复杂性T(n)通常不小于 O(an)，这里a是子问题的个数。用递推递归求解的思路仍是先考虑最简情况，再考虑复杂情况与较简情况关系。程序的完全正确性由其部分正确性和终止性两部分构成。2022-12-20计算计算法设计与分析39通信信道上允许传输的单词 已知在通信信道上传输的单词只能由a、b和c三个字母组成并且其中不得有两个字母a连续出现。请编写一个程序生成所有在通信信道上允许传输的长度为n的单词。将这样的单词称为长将这样的单词称为长度为度为n的合法单词。的合法单词。我们该如何来考虑编写这个程序呢？我们该如何来考虑编写

26、这个程序呢？1、先分析最简单情况的解。2、再分析复杂情况如何由较简情况组成。2022-12-20计算计算法设计与分析40通信信道上允许传输的单词 应该是长度n=1的单词。此问题中最简单的情况是什么？此问题中最简单的情况是什么？长度为1的合法单词只有三个，即a、b和c。下面我们再考虑长度为n(n 1)的合法单词是如何由长度n 1的合法单词构成的。2022-12-20计算计算法设计与分析41通信信道上允许传输的单词 把长度为n 合法单词w去掉最前面的一个符号后所剩下的就是长度为n 1的单词w。显然w仍然应该是合法单词。如何考虑用长度如何考虑用长度n 1n 1的合法单词来构的合法单词来构成长度成长度

27、n n的合法单词呢？的合法单词呢？于是有：w=a+wb+wc+w这里用符号+表示符号串的连接运算。2022-12-20计算计算法设计与分析42通信信道上允许传输的单词 先考虑w=a+w的情况：于是有：w=a+b+wa+c+w 因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。将长度为将长度为n的合法单词命名为的合法单词命名为Legal(n)。2022-12-20计算计算法设计与分析43通信信道上允许传输的单词 先考虑w=a+w的情况：于是有：Legal(n)=a+b+Legal(n 2)a+c+Legal

28、(n 2)因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。2022-12-20计算计算法设计与分析44通信信道上允许传输的单词 再考虑w=b+w和w=c+w的情况：于是有：Legal(n)=b+Legal(n 1)c+Legal(n 1)这里的w可以为任意的长度为n 1的合法单词。2022-12-20计算计算法设计与分析45通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Leg

29、al(n 1)c+Legal(n 1)现在发生了一个新的情况！现在发生了一个新的情况！什么情况？什么情况？2022-12-20计算计算法设计与分析46通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Legal(n 1)c+Legal(n 1)这是个两步递归！可是我们只考虑了n=1这一种最简单情况！要增加要增加n=0的情况。的情况。2022-12-20计算计算法设计与分析47通信信道上允许传输的单词 综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系

30、：Legal(n)=a+b+Legal(n 2)a+c+Legal(n 2)b+Legal(n 1)c+Legal(n 1)我们令当n=0时的合法单词为空串，即 Legal(0)=。2022-12-20计算计算法设计与分析48通信信道上允许传输的单词 综合n 为 0和1的最简单情况后，有：Legal(n)=n=0b n=1c n=1a n=1a+b+Legal(n 2)n 1a+c+Legal(n 2)n 1b+Legal(n 1)n 1c+Legal(n 1)n 12022-12-20计算计算法设计与分析49程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序

31、要打印出所有在通信信道上传输的长度为n的合法单词。现在你头脑里想象的打印现在你头脑里想象的打印 过程该是什么样子的呢？过程该是什么样子的呢？2022-12-20计算计算法设计与分析50程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。我想：这个程序应该是从左向右逐个符号地生成每一个长度为n的合法单词。每生成一个合法单词，就把它打印出去。2022-12-20计算计算法设计与分析51程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。

32、我想：那么，这个程序就应该有个存放这个长度为n的合法单词的变量，就叫它wn。干脆把这个程序叫做Legal(w,n)好了。2022-12-20计算计算法设计与分析52程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。我想：那么，什么时候就该打印合法单词wn呢？那不就是n=0的时候吗？2022-12-20计算计算法设计与分析53程序设计的思考 现在就让我们来设计这个程序吧！现在就让我们来设计这个程序吧！这个程序要打印出所有在通信信道上传输的长度为n的合法单词。aha!I got it!按照递归规则，从n开始，就是从

33、左至右，将合法的符号放进w；每放一个符号，n就减一。当n个符号全都放进去了，就是n=0了，就把w打印出去。2022-12-20计算计算法设计与分析54打印合法单词的程序 Legal(wn,int k)if(k=0)print w else if(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)else Legal(w+a+b,k2);Legal(w+a+c,k2);Legal(w+b,k1);Legal(w+c,k1)main(int n)int wn=0;Legal(wn,n)考虑运算考虑运算w+x。2022-12-20计算计算法设计与分析55打印合

34、法单词的程序 Legal(wn,int k)if(k=0)print w else if(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)else Legal(w+a+b,k2);Legal(w+a+c,k2);Legal(w+b,k1);Legal(w+c,k1)main(int n)int wn=0;Legal(wn,n)w+x就是就是wnk=x。w+x+y就是就是wnk=x;wnk+1=y。2022-12-20计算计算法设计与分析56打印合法单词的程序 我们让递归元的初值为0，终止值为n，而递归元的递减方式改成加法，即n+1。于是这个程序还可改写

35、成下面的样子：考虑到运算考虑到运算w+x的方便我们的方便我们可以改变递归的方向。可以改变递归的方向。2022-12-20计算计算法设计与分析57打印合法单词的程序 Legal(wn,int k)if(k=n)print w else if(k=n1)Legal(w+a,k+1);Legal(w+b,k+1);Legal(w+c,k+1)else Legal(w+a+b,k+2);Legal(w+a+c,k+2);Legal(w+b,k+1);Legal(w+c,k+1)main(int n)int wn=0;Legal(wn,0)k=n时递归时递归终止。终止。递归元用加递归元用加法来递减。法来

36、递减。直接将数组直接将数组w的第的第k个分量赋值为个分量赋值为a。递归元的初递归元的初值赋为值赋为0。请同学们自己变成来请同学们自己变成来具体实现这个程序。具体实现这个程序。2022-12-20计算计算法设计与分析58算法的时间复杂性 这个算法是一个递推的递归式，并且是一个两步递归。由前面的基本分析可以断定其复杂性应该是指数的，即T(n)=O(an)。这个算法中的子任务为2，因此它的时间复杂性应该不会低于O(2n)。O(1+3)n)。这个程序的时间复杂性是 它的复杂性实际上决定于合法单词的数量。2022-12-20计算计算法设计与分析59通信信道上允许传输的单词 计算通信信道上允许传输的合法单

37、词个数。解：令h(n)为的长度n的合法单词个数。由前面的讨论我们有：最简单情况时h(0)=1，h(1)=3。当n2时：h(n)=2 h(n1)+2 h(n2)求解这个递归方程可得：(2+3)23(1+3)n+h(n)=(2+3)23(13)n这个递归函数也是著这个递归函数也是著名的斐波拉契函数。名的斐波拉契函数。有趣的是，对于任意的有趣的是，对于任意的n，这，这个无理式的结果都是整数。个无理式的结果都是整数。2022-12-20计算计算法设计与分析60斐波那契递归式 斐波那契递归式：0 n=0f(n)=1 n=1 f(n1)+f(n2)n 1。按照斐波那契递归式得到的序列称为斐波那契序列，序列

38、中的项称为斐波那契数。这是一个非常重要的序列。2022-12-20计算计算法设计与分析61斐波那契递归式 斐波那契递归式：0 n=0f(n)=1 n=1 f(n1)+f(n2)n 1。斐波那契数列的通项公式为：h(n)=151+52()n 151 52()n2022-12-20计算计算法设计与分析62一般的斐波那契递归式 一般的斐波那契递归式为如下形式：a n=0f(n)=b n=1 cf(n1)+df(n2)n 1。其通解为 f(n)=c1q1n+c2q2n。其中q1和q2为其特征方程的根，系数c1和c2由初始条件来决定。2022-12-20计算计算法设计与分析63分治法的基本思想 将规模为

39、n的问题分解为k个规模较小的子问题，子问题互相独立且与原问题相同。递归地求解这些子问题问题。然后将子问题的解合并得到原问题的解。思考的基本途径是：思考的基本途径是：1 1、先考虑最简单情况的解；、先考虑最简单情况的解；2 2、再分析复杂情况与较简情况之间关系。、再分析复杂情况与较简情况之间关系。2022-12-20计算计算法设计与分析64分治法的一般模式 Divide-and-Conquer(P)if(|P|=n0)return Adhoc(P);/若P的规模不超过阈值n0可直接求解并结束递归/divide P into smaller subinstants P1,.,Pk;for(i=1;

40、i=k;i+)/逐个求子问题解yi/yi=Divide-and-Conquer(Pi);return Merge(y1,yk);/返回P的解/Merge(y1,yk)将子问题解合成P的解/2022-12-20计算计算法设计与分析65分治递归的复杂性 决定分治递归复杂性的因素有：递归元递减方式nb；子问题的个数a；递减步长b;合并开销函数D(n)。可以是除法或减法。若是减法，则时间复杂性一可以是除法或减法。若是减法，则时间复杂性一般都是指数型的，即般都是指数型的，即T(n)=O(an)。减少子问题个数减少子问题个数a可以减低时间复杂性。可以减低时间复杂性。增加递减步长增加递减步长b可以减低时间复杂性。可以减低时间复杂性。D(n)越低，时间复杂性越低。越低，时间复杂性越低。