递推递归的复杂性分析课件.ppt
2023/4/1,计算计算法设计与分析,1,2.3 递推递归的复杂性分析,2023/4/1,计算计算法设计与分析,2,递归复杂性的一般形式,一般的，递归关系描述为递归方程：,其中，a是子问题个数，b是递减步长，表示递减方式，D(n)是合成子问题的开销。,通常，递归元的递减方式有两种：,1、除法，即n/b，的形式；2、减法，即n b，的形式。,分治,递推,2023/4/1,计算计算法设计与分析,3,递推关系与递归,算术序列：h0,h0+q,h0+2q,h0+nq,.或为递归式：h(n)=h(n 1)+q，h(0)=h0。,几何序列：h0,qh0,q2h0,qnh0,.或为递归式：h(n)=qh(n1)，h(0)=h0。,如果递归式的递减方式是减法的话，则递归式按其递归元就形成一个递推序列。,2023/4/1,计算计算法设计与分析,4,递推递归的时间复杂性,这里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)=,在通常的情况下递推递归的时间复杂性为指数函数。,2023/4/1,计算计算法设计与分析,5,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,所谓相互交叠的圆是指两个圆相交在不同的两点。,2023/4/1,计算计算法设计与分析,6,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,令h(n)为平面上有n个互相交叠的圆所形成的区域数。,h(n)=?,让我们先从最简单的情况来考虑。,2023/4/1,计算计算法设计与分析,7,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,令h(n)为平面上有n个互相交叠的圆所形成的区域数。,显然h(0)=1。,h(1)=2。,h(2)=4。,h(3)=8。,h(4)=？,h(4)=14,2023/4/1,计算计算法设计与分析,8,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,令h(n)为平面上有n个互相交叠的圆所形成的区域数。,h(n)=?,我们仍然不知道。我们该怎么做呢？,2023/4/1,计算计算法设计与分析,9,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,令h(n)为平面上有n个互相交叠的圆所形成的区域数。,这时要考虑复杂情况与较简单情况之间关系，即复杂情况是怎样由较简单情况构成的。,2023/4/1,计算计算法设计与分析,10,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,假设前面n 1个圆形成h(n1)个区域。,现放进第n个圆与前n1个圆交叠。,让我们来考虑把这第n个圆交叠上去会造成区域数发生什么样的变化呢？,2023/4/1,计算计算法设计与分析,11,n个互相交叠的圆的区域数,在平面一般位置上有n个互相交叠的圆所形成的区域数是多少？,假设前面n 1个圆形成h(n1)个区域。,现放进第n个圆与前n1个圆交叠。,第n个圆与前n1个圆都相交于两点，于是有2(n1)个交点。这2(n1)个点将第n个圆分成2(n1)条弧，而每条弧又将某个区域一分为二，因此新增加的区域数应为2(n1)。,2023/4/1,计算计算法设计与分析,12,n个互相交叠的圆的区域数,在平面一般位置上有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。,2023/4/1,计算计算法设计与分析,13,棋盘覆盖问题,一个2k2k特殊棋盘是其中含有一个特殊方格的棋盘，左下图为k=2的一个特殊棋盘。,现在任给定一个2k2k特殊棋盘，要用右下图所示的L型骨牌来无重叠的覆盖它。,在2k2k的棋盘覆盖中要用到(4k1)/3个L型骨牌。,2023/4/1,计算计算法设计与分析,14,棋盘覆盖问题,让我们先来考虑最简单的情况：,什么是最简单的情况？,最简单情况是k=0。这时棋盘有2020=1个格子，即只有一个特殊格子。这时棋盘已被完全覆盖，无须再做什么了。下面我们来考虑复杂情况是怎样由较简单情况构成的。,2023/4/1,计算计算法设计与分析,15,棋盘覆盖问题的分析,当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：,特殊方格必定位于4个子棋盘之一中。,而这四个子棋盘却不一致。递归求解是将问题归结到较小规模的同一问题，这就需要将三个正常子棋盘也转化成特殊棋盘。,2023/4/1,计算计算法设计与分析,16,棋盘覆盖问题的分析,当k0时，将2k2k棋盘分割成4个2k12k1的子棋盘，如右下图所示：,特殊方格必定位于4个子棋盘之一中。,为此，可用一个L型骨牌覆盖三个正常子棋盘的会合处，如左图所示。,这次覆盖后四个子棋盘都是特殊棋盘了。,2023/4/1,计算计算法设计与分析,17,棋盘覆盖的算法,棋盘覆盖(参数表)如果是单个格子，则返回；将棋盘划分成尺寸为一半的子棋盘；判断特殊方格在哪个子棋盘中，再用相应L型骨牌覆盖相应结合部，即不含特殊方格的部分在结合部的三个方格；并记下它们的位置，作为各部分的特殊方格；依次对左上角、右上角、右下角和左下角四个子棋盘进行棋盘覆盖；,2023/4/1,计算计算法设计与分析,18,棋盘覆盖算法中的参数,算法的形参表中需要的参数有：递归元：棋盘尺寸为2n。每轮递归时将n减 1，则棋盘尺寸减半；当n为0时递归终止。棋盘位置：棋盘左上角方格的行列号tr和tc。特殊方格位置：特殊方格的行列号dr和dc。,参数表中应有哪些参数呢？,递归元定义为int n棋盘位置定义为int tr,tc。特殊方格位置定义为int dr,dc。,2023/4/1,计算计算法设计与分析,19,棋盘覆盖算法中其它变量,除了形参表中的那些参数外，棋盘覆盖程序中还需要如下的变量：表示棋盘的变量。表示L型骨牌覆盖顺序的变量。棋盘尺寸的变量。各子棋盘在结合部的方格位置。各子棋盘的特殊方格的位置。,除形参外，算法中还应有哪些变量呢？,为什么要设这个变量呢？,2023/4/1,计算计算法设计与分析,20,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。,不设此变量也可以。但因s=2n，则每轮递归中都要做求2n的幂运算。设变量s后，只需初始时计算一次s=2n，以后只要做s=s/2即可。这样降低了递归中的运算强度。,2023/4/1,计算计算法设计与分析,21,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s，其初值为2n。,四个子棋盘的排序为,结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。,2023/4/1,计算计算法设计与分析,22,棋盘覆盖算法中其它变量,棋盘定义为int Board2n2n，初值为全0。覆盖顺序变量定义为int tile，其初值为0。棋盘尺寸的变量定义为int s。结合部的方格位置定义为int jr4,jc4。各子棋盘的特殊方格的位置定义为int Sr4,Sc4。,将棋盘覆盖程序取名为CoverBoard；,2023/4/1,计算计算法设计与分析,23,棋盘覆盖的算法,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),若只有一个格子，则终止递归。,注意递归元的递减是在这里做的。s是减半后的子棋盘尺寸。,在对结合部覆盖之前将覆盖序号tile加一。,2023/4/1,计算计算法设计与分析,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、覆盖子棋盘结合部并将四个特殊方格的位置写入sr 和sc。,依次对四个子棋盘进行覆盖。,覆盖左上角的子棋盘。,覆盖右上角的子棋盘。,覆盖右下角的子棋盘。,覆盖左下角的子棋盘。,2023/4/1,计算计算法设计与分析,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,sr1,sc1)；CoverBoard(n,tr+s,tc+s,sr2,sc2)CoverBoard(n,tr,tc+s,sr3,sc3),依次对四个子棋盘进行覆盖。,覆盖左上角的0号子棋盘。,覆盖右上角的1号子棋盘。,覆盖右下角的2号子棋盘。,覆盖左下角的3号子棋盘。,2023/4/1,计算计算法设计与分析,26,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr,dc)落在那个子棋盘：,覆盖结合部并确定各子棋盘特殊方格位置。,2023/4/1,计算计算法设计与分析,27,Coverjoin的实现,计算结合部方格位置：,tr是0区和1区的首行，tc是0区和3区的首列;tr+s是3区和2区的首行;tc+s是1区和2区的首列,tr,tc,2023/4/1,计算计算法设计与分析,28,Coverjoin的实现,计算结合部方格位置：,tr,tc,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+s1,jr1=tr+s1;jc1=tc+s,jr2=tr+s;jc2=tc+s,jr3=tr+s;jc3=tc+s1,2023/4/1,计算计算法设计与分析,29,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr,dc)落在那个子棋盘：,我们可以依据结合部方格的行号和列号来判断特殊方格落在哪个子棋盘中。,tr,tc,jr0=tr+s1;jc0=tc+s1;jr1=tr+s;jc1=tc+s1;jr2=tr+s;jc2=tc+s;jr3=tr+s1;jc3=tc+s;,2023/4/1,计算计算法设计与分析,30,Coverjoin的实现,计算结合部方格位置：,判断特殊方格(dr,dc)落在那个子棋盘：,覆盖结合部并确定各子棋盘特殊方格位置。,if(dr=jc1)r=1else if(dr=jr2,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指明了这点。,2023/4/1,计算计算法设计与分析,31,Coverjoin的实现,覆盖结合部并确定各子棋盘特殊方格位置：if(r=0)sr0=dr;sc0=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=1,2,3 elseif(r=1)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,2,3 elseif(r=2)sr2=dr;sc2=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,3 elseif(r=3)sr1=dr;sc1=dc;Boardjrkjck=tile;srk=jrk;sck=jck;k=0,1,2;,注意：此处由于幻灯片篇幅的原因，简写成这样，实际表示对于k=1,2,3，执行Boardjrkjck=tile;srk=jrk;sck=jck;，即覆盖相应格子，并将其作为对应子棋盘的特殊方格。下面亦如此。,2023/4/1,计算计算法设计与分析,32,Coverjoin的实现,覆盖结合部并确定各子棋盘特殊方格位置也可以用如下的语句来实现：srr=dr;scr=dc;for(k=0,kr)Boardjrkjck=tile;srk=jrk;sck=jck;,特殊子棋盘的特殊方格还是原来的。,对每个非特殊子棋盘，则覆盖其结合部的方格并将其作为该子棋盘的特殊方格。,由于这个操作可以用此简单表示，所以才在上一张幻灯片上采用了简记的方式。,2023/4/1,计算计算法设计与分析,33,棋盘覆盖算法的主程序,main(int n,int dr,int dc)int s=2n int Boardss=0;int tile=0;CoverBoard(n,0,0,dr,dc);,请同学们自己编程来具体实现这个程序。,2023/4/1,计算计算法设计与分析,34,棋盘覆盖算法的正确性,要证明一个算法的正确性，需要证明两点：(1)算法的部分正确性；(2)算法的终止性。下面我们用归纳法证明棋盘覆盖算法的部分正确性：,2023/4/1,计算计算法设计与分析,35,棋盘覆盖算法的部分正确性,归纳基础：k=0时，特殊棋盘仅含一个特殊方格，显然已经正确覆盖。假设对2k1的特殊棋盘均可正确覆盖。对2k的特殊棋盘，算法划分为四个2k1的子棋盘。用一块L型骨牌覆盖三个正常子棋盘的结合处后，恰形成四个2k1的特殊棋盘。由归纳假设，它们均可被正确覆盖。因而也正确覆盖了2k的特殊棋盘。由归纳法可知，棋盘覆盖算法是部分正确。,2023/4/1,计算计算法设计与分析,36,棋盘覆盖算法的终止性,算法的终止性：递归终止条件为递归元size为1时递归终止。递归元size的初值为2k。每次递归时递归元减半，即size=size/2；因此，必然在有穷步内递减为1。所以此算法必定终止。,由部分正确性和终止性可知，此算法是完全正确的。,2023/4/1,计算计算法设计与分析,37,棋盘覆盖算法的复杂性,设T(k)是棋盘覆盖算法覆盖2k2k的棋盘所需要的时间，则T(k)满足如下递归方程：,递归元递减方式是减法，故此分治法实质是递推关系。由a=4可知T(k)=O(4k)。,覆盖2k2k的棋盘要用(4k1)/3个L型骨牌，故此算法是一个在渐进意义下最优的算法。,2023/4/1,计算计算法设计与分析,38,小结,用减法方式递减的递归式按其递归元形成一个递推序列。递推关系的递归程序的时间复杂性T(n)通常不小于 O(an)，这里a是子问题的个数。用递推递归求解的思路仍是先考虑最简情况，再考虑复杂情况与较简情况关系。程序的完全正确性由其部分正确性和终止性两部分构成。,2023/4/1,计算计算法设计与分析,39,通信信道上允许传输的单词,已知在通信信道上传输的单词只能由a、b和c三个字母组成并且其中不得有两个字母a连续出现。请编写一个程序生成所有在通信信道上允许传输的长度为n的单词。,将这样的单词称为长度为n的合法单词。,我们该如何来考虑编写这个程序呢？,1、先分析最简单情况的解。2、再分析复杂情况如何由较简情况组成。,2023/4/1,计算计算法设计与分析,40,通信信道上允许传输的单词,应该是长度n=1的单词。,此问题中最简单的情况是什么？,长度为1的合法单词只有三个，即a、b和c。,下面我们再考虑长度为n(n 1)的合法单词是如何由长度n 1的合法单词构成的。,2023/4/1,计算计算法设计与分析,41,通信信道上允许传输的单词,把长度为n 合法单词w去掉最前面的一个符号后所剩下的就是长度为n 1的单词w。显然w仍然应该是合法单词。,如何考虑用长度n 1的合法单词来构成长度n的合法单词呢？,于是有：,这里用符号+表示符号串的连接运算。,2023/4/1,计算计算法设计与分析,42,通信信道上允许传输的单词,先考虑w=a+w的情况：,于是有：,因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。,将长度为n的合法单词命名为Legal(n)。,2023/4/1,计算计算法设计与分析,43,通信信道上允许传输的单词,先考虑w=a+w的情况：,于是有：,因为通信信道上的合法单词中不允许出现连续的a，所以w只能以b或者c开头。于是w=b+w或者w=c+w。这里w为任意的长度为n 2的合法单词。,2023/4/1,计算计算法设计与分析,44,通信信道上允许传输的单词,再考虑w=b+w和w=c+w的情况：,于是有：,这里的w可以为任意的长度为n 1的合法单词。,2023/4/1,计算计算法设计与分析,45,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,现在发生了一个新的情况！,什么情况？,2023/4/1,计算计算法设计与分析,46,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,这是个两步递归！可是我们只考虑了n=1这一种最简单情况！,要增加n=0的情况。,2023/4/1,计算计算法设计与分析,47,通信信道上允许传输的单词,综合起来可以得到长度为n的合法单词与长度较短的合法单词之间有如下的关系：,我们令当n=0时的合法单词为空串，即 Legal(0)=。,2023/4/1,计算计算法设计与分析,48,通信信道上允许传输的单词,综合n 为 0和1的最简单情况后，有：,2023/4/1,计算计算法设计与分析,49,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,2023/4/1,计算计算法设计与分析,50,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,我想：这个程序应该是从左向右逐个符号地生成每一个长度为n的合法单词。每生成一个合法单词，就把它打印出去。,2023/4/1,计算计算法设计与分析,51,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,我想：那么，这个程序就应该有个存放这个长度为n的合法单词的变量，就叫它wn。,干脆把这个程序叫做Legal(w,n)好了。,2023/4/1,计算计算法设计与分析,52,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,我想：那么，什么时候就该打印合法单词wn呢？,那不就是n=0的时候吗？,2023/4/1,计算计算法设计与分析,53,程序设计的思考,现在就让我们来设计这个程序吧！,这个程序要打印出所有在通信信道上传输的长度为n的合法单词。,aha!I got it!,按照递归规则，从n开始，就是从左至右，将合法的符号放进w；每放一个符号，n就减一。当n个符号全都放进去了，就是n=0了，就把w打印出去。,2023/4/1,计算计算法设计与分析,54,打印合法单词的程序,Legal(wn,int k)if(k=0)print w elseif(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)elseLegal(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。,2023/4/1,计算计算法设计与分析,55,打印合法单词的程序,Legal(wn,int k)if(k=0)print w elseif(k=1)Legal(w+a,k1);Legal(w+b,k1);Legal(w+c,k1)elseLegal(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。,2023/4/1,计算计算法设计与分析,56,打印合法单词的程序,我们让递归元的初值为0，终止值为n，而递归元的递减方式改成加法，即n+1。于是这个程序还可改写成下面的样子：,考虑到运算w+x的方便我们可以改变递归的方向。,2023/4/1,计算计算法设计与分析,57,打印合法单词的程序,Legal(wn,int k)if(k=n)print w elseif(k=n1)Legal(w+a,k+1);Legal(w+b,k+1);Legal(w+c,k+1)elseLegal(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时递归终止。,递归元用加法来递减。,直接将数组w的第k个分量赋值为a。,递归元的初值赋为0。,请同学们自己变成来具体实现这个程序。,2023/4/1,计算计算法设计与分析,58,算法的时间复杂性,这个算法是一个递推的递归式，并且是一个两步递归。由前面的基本分析可以断定其复杂性应该是指数的，即T(n)=O(an)。这个算法中的子任务为2，因此它的时间复杂性应该不会低于O(2n)。,它的复杂性实际上决定于合法单词的数量。,2023/4/1,计算计算法设计与分析,59,通信信道上允许传输的单词,计算通信信道上允许传输的合法单词个数。解：令h(n)为的长度n的合法单词个数。由前面的讨论我们有：最简单情况时h(0)=1，h(1)=3。当n2时：h(n)=2 h(n1)+2 h(n2),求解这个递归方程可得：,这个递归函数也是著名的斐波拉契函数。,有趣的是，对于任意的n，这个无理式的结果都是整数。,2023/4/1,计算计算法设计与分析,60,斐波那契递归式,斐波那契递归式：,按照斐波那契递归式得到的序列称为斐波那契序列，序列中的项称为斐波那契数。这是一个非常重要的序列。,2023/4/1,计算计算法设计与分析,61,斐波那契递归式,斐波那契递归式：,2023/4/1,计算计算法设计与分析,62,一般的斐波那契递归式,一般的斐波那契递归式为如下形式：,其通解为 f(n)=c1q1n+c2q2n。其中q1和q2为其特征方程的根，系数c1和c2由初始条件来决定。,2023/4/1,计算计算法设计与分析,63,分治法的基本思想,将规模为n的问题分解为k个规模较小的子问题，子问题互相独立且与原问题相同。递归地求解这些子问题问题。然后将子问题的解合并得到原问题的解。,思考的基本途径是：1、先考虑最简单情况的解；2、再分析复杂情况与较简情况之间关系。,2023/4/1,计算计算法设计与分析,64,分治法的一般模式,Divide-and-Conquer(P)if(|P|=n0)return Adhoc(P);/若P的规模不超过阈值n0可直接求解并结束递归/divide P into smaller subinstants P1,.,Pk;for(i=1;i=k;i+)/逐个求子问题解yi/yi=Divide-and-Conquer(Pi);return Merge(y1,yk);/返回P的解/Merge(y1,yk)将子问题解合成P的解/,2023/4/1,计算计算法设计与分析,65,分治递归的复杂性,决定分治递归复杂性的因素有：递归元递减方式nb；子问题的个数a；递减步长b;合并开销函数D(n)。,可以是除法或减法。若是减法，则时间复杂性一般都是指数型的，即T(n)=O(an)。,减少子问题个数a可以减低时间复杂性。,增加递减步长b可以减低时间复杂性。,D(n)越低，时间复杂性越低。,
