遞推遞歸的復(fù)雜性分析課件

2.3遞推遞歸的復(fù)雜性分析9/21/20231計(jì)算計(jì)算法設(shè)計(jì)與分析2.3遞推遞歸的復(fù)雜性分析8/6/20231計(jì)算計(jì)算法設(shè)遞歸復(fù)雜性的一般形式一般的，遞歸關(guān)系描述為遞歸方程：1n=1aT(n~b)+D(n)n＞1T(n)=其中，a是子問題個(gè)數(shù)，b是遞減步長，~表示遞減方式，D(n)是合成子問題的開銷。通常，遞歸元的遞減方式~有兩種：1、除法，即n/b，的形式；2、減法，即n–b，的形式。分治遞推9/21/20232計(jì)算計(jì)算法設(shè)計(jì)與分析遞歸復(fù)雜性的一般形式一般的，遞歸關(guān)系描述為遞歸方程：遞推關(guān)系與遞歸算術(shù)序列：h0,h0+q,h0+2q,…,h0+nq,….或?yàn)檫f歸式：h(n)=h(n–1)+q，h(0)=h0。幾何序列：h0,qh0,q2h0,…,qnh0,….或?yàn)檫f歸式：h(n)=qh(n–1)，h(0)=h0。如果遞歸式的遞減方式是減法的話，則遞歸式按其遞歸元就形成一個(gè)遞推序列。9/21/20233計(jì)算計(jì)算法設(shè)計(jì)與分析遞推關(guān)系與遞歸算術(shù)序列：h0,h0+q,h0+2q,…遞推遞歸的時(shí)間復(fù)雜性

k–1

i=0=akT(1)+aiD(n–ib)這里k=n/b。不失一般性令b=1，則k=n。若設(shè)D(n)為常數(shù)，則有T(n)=

O(an)。若~為減法，即n–b，則有：T(n)=aT(n–b)+D(n)=a(aT(n–2b)+D(n–b))+D(n)=

k–1

i=0=ak+aiD(n–ib)在通常的情況下遞推遞歸的時(shí)間復(fù)雜性為指數(shù)函數(shù)。9/21/20234計(jì)算計(jì)算法設(shè)計(jì)與分析遞推遞歸的時(shí)間復(fù)雜性k–1=akT(1)+n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？所謂相互交疊的圓是指兩個(gè)圓相交在不同的兩點(diǎn)。9/21/20235計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？令h(n)為平面上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)。h(n)=?讓我們先從最簡單的情況來考慮。9/21/20236計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？令h(n)為平面上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)。顯然h(0)=1。h(1)=2。h(2)=4。h(3)=8。h(4)=？h(4)=149/21/20237計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？令h(n)為平面上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)。h(n)=?我們?nèi)匀徊恢?。我們?cè)撛趺醋瞿兀?/21/20238計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？令h(n)為平面上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)。這時(shí)要考慮復(fù)雜情況與較簡單情況之間關(guān)系，即復(fù)雜情況是怎樣由較簡單情況構(gòu)成的。9/21/20239計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？假設(shè)前面n–1個(gè)圓形成h(n–1)個(gè)區(qū)域。現(xiàn)放進(jìn)第n個(gè)圓與前n–1個(gè)圓交疊。讓我們來考慮把這第n個(gè)圓交疊上去會(huì)造成區(qū)域數(shù)發(fā)生什么樣的變化呢？9/21/202310計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？假設(shè)前面n–1個(gè)圓形成h(n–1)個(gè)區(qū)域。現(xiàn)放進(jìn)第n個(gè)圓與前n–1個(gè)圓交疊。第n個(gè)圓與前n–1個(gè)圓都相交于兩點(diǎn)，于是有2(n–1)個(gè)交點(diǎn)。這2(n–1)個(gè)點(diǎn)將第n個(gè)圓分成2(n–1)條弧，而每條弧又將某個(gè)區(qū)域一分為二，因此新增加的區(qū)域數(shù)應(yīng)為2(n–1)。9/21/202311計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)是多少？令h(n)為平面上有n個(gè)互相交疊的圓所形成的區(qū)域數(shù)。于是便得到如下的遞歸式：h(n)=h(n–1)+2(n–1)。這個(gè)遞推遞歸式有一個(gè)簡單的通項(xiàng)公式：h(n)=h(n–1)+2(n–1)。h(n–2)+2(n–2)+2(n–1)h(n–3)+2(n–3)+2(n–2)+2(n–1)h(1)+2(1)+2(2)+…+2(n–1)2+2n(n–1)/2=n2–n+2。注意此公式對(duì)h(0)不成立！n>0。9/21/202312計(jì)算計(jì)算法設(shè)計(jì)與分析n個(gè)互相交疊的圓的區(qū)域數(shù)在平面一般位置上有n個(gè)互相交疊的圓所棋盤覆蓋問題一個(gè)2k×2k特殊棋盤是其中含有一個(gè)特殊方格的棋盤，左下圖為k=2的一個(gè)特殊棋盤。現(xiàn)在任給定一個(gè)2k×2k特殊棋盤，要用右下圖所示的L型骨牌來無重疊的覆蓋它。 111222333444555在2k×2k的棋盤覆蓋中要用到(4k–1)/3個(gè)L型骨牌。9/21/202313計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋問題一個(gè)2k×2k特殊棋盤是其中含有一個(gè)特殊方格的棋棋盤覆蓋問題讓我們先來考慮最簡單的情況：什么是最簡單的情況？最簡單情況是k=0。這時(shí)棋盤有20×20=1個(gè)格子，即只有一個(gè)特殊格子。這時(shí)棋盤已被完全覆蓋，無須再做什么了。下面我們來考慮復(fù)雜情況是怎樣由較簡單情況構(gòu)成的。9/21/202314計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋問題讓我們先來考慮最簡單的情況：什么是最簡單的情況？棋盤覆蓋問題的分析當(dāng)k>0時(shí)，將2k×2k棋盤分割成4個(gè)2k–1×2k–1的子棋盤，如右下圖所示：2k–1×2k–12k–1×2k–12k–1×2k–12k–1×2k–1特殊方格必定位于4個(gè)子棋盤之一中。而這四個(gè)子棋盤卻不一致。遞歸求解是將問題歸結(jié)到較小規(guī)模的同一問題，這就需要將三個(gè)正常子棋盤也轉(zhuǎn)化成特殊棋盤。9/21/202315計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋問題的分析當(dāng)k>0時(shí)，將2k×2k棋盤分割成4個(gè)2k棋盤覆蓋問題的分析當(dāng)k>0時(shí)，將2k×2k棋盤分割成4個(gè)2k–1×2k–1的子棋盤，如右下圖所示：2k–1×2k–12k–1×2k–12k–1×2k–12k–1×2k–1特殊方格必定位于4個(gè)子棋盤之一中。為此，可用一個(gè)L型骨牌覆蓋三個(gè)正常子棋盤的會(huì)合處，如左圖所示。這次覆蓋后四個(gè)子棋盤都是特殊棋盤了。9/21/202316計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋問題的分析當(dāng)k>0時(shí)，將2k×2k棋盤分割成4個(gè)2k棋盤覆蓋的算法棋盤覆蓋(參數(shù)表){⑴如果是單個(gè)格子，則返回；⑵將棋盤劃分成尺寸為一半的子棋盤；⑶判斷特殊方格在哪個(gè)子棋盤中，再用相應(yīng)L型骨牌覆蓋相應(yīng)結(jié)合部，即不含特殊方格的部分在結(jié)合部的三個(gè)方格；并記下它們的位置，作為各部分的特殊方格；⑷依次對(duì)左上角、右上角、右下角和左下角四個(gè)子棋盤進(jìn)行棋盤覆蓋；}9/21/202317計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋的算法棋盤覆蓋(參數(shù)表){8/6/202317計(jì)算棋盤覆蓋算法中的參數(shù)算法的形參表中需要的參數(shù)有：遞歸元：棋盤尺寸為2n。每輪遞歸時(shí)將n減1，則棋盤尺寸減半；當(dāng)n為0時(shí)遞歸終止。棋盤位置：棋盤左上角方格的行列號(hào)tr和tc。特殊方格位置：特殊方格的行列號(hào)dr和dc。參數(shù)表中應(yīng)有哪些參數(shù)呢？遞歸元定義為intn棋盤位置定義為inttr,tc。特殊方格位置定義為intdr,dc。9/21/202318計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法中的參數(shù)算法的形參表中需要的參數(shù)有：參數(shù)表中應(yīng)有棋盤覆蓋算法中其它變量除了形參表中的那些參數(shù)外，棋盤覆蓋程序中還需要如下的變量：表示棋盤的變量。表示L型骨牌覆蓋順序的變量。棋盤尺寸的變量。各子棋盤在結(jié)合部的方格位置。各子棋盤的特殊方格的位置。除形參外，算法中還應(yīng)有哪些變量呢？內(nèi)部變量全局變量為什么要設(shè)這個(gè)變量呢？9/21/202319計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法中其它變量除了形參表中的那些參數(shù)外，棋盤覆蓋程序棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints，其初值為2n。不設(shè)此變量也可以。但因s=2n，則每輪遞歸中都要做求2n的冪運(yùn)算。設(shè)變量s后，只需初始時(shí)計(jì)算一次s=2n，以后只要做s=s/2即可。這樣降低了遞歸中的運(yùn)算強(qiáng)度。9/21/202320計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints，其初值為2n。0132四個(gè)子棋盤的排序?yàn)榻Y(jié)合部的方格位置定義為intjr[4],jc[4]。各子棋盤的特殊方格的位置定義為intSr[4],Sc[4]。9/21/202321計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][2n]，初值為全0。覆蓋順序變量定義為inttile，其初值為0。棋盤尺寸的變量定義為ints。結(jié)合部的方格位置定義為intjr[4],jc[4]。各子棋盤的特殊方格的位置定義為intSr[4],Sc[4]。將棋盤覆蓋程序取名為CoverBoard；9/21/202322計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法中其它變量棋盤定義為intBoard[2n][棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return;n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}若只有一個(gè)格子，則終止遞歸。注意遞歸元的遞減是在這里做的。s是減半后的子棋盤尺寸。在對(duì)結(jié)合部覆蓋之前將覆蓋序號(hào)tile加一。9/21/202323計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return();n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}Coverjoin完成以下功能：1、計(jì)算結(jié)合部的方格的位置；2、判斷特殊方格位置；3、覆蓋子棋盤結(jié)合部并將四個(gè)特殊方格的位置寫入sr[]和sc[]。依次對(duì)四個(gè)子棋盤進(jìn)行覆蓋。覆蓋左上角的子棋盤。覆蓋右上角的子棋盤。覆蓋右下角的子棋盤。覆蓋左下角的子棋盤。9/21/202324計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,棋盤覆蓋的算法voiceCoverBoard(n,tr,tc,dr,dc){if(n=0)return();n=n–1;s=s/2;tile++;Coverjoin;CoverBoard(n,tr,tc,sr[0],sc[0]);CoverBoard(n,tr+s,tc,sr[1],sc[1])；CoverBoard(n,tr+s,tc+s,sr[2],sc[2])CoverBoard(n,tr,tc+s,sr[3],sc[3])}依次對(duì)四個(gè)子棋盤進(jìn)行覆蓋。覆蓋左上角的0號(hào)子棋盤。覆蓋右上角的1號(hào)子棋盤。覆蓋右下角的2號(hào)子棋盤。覆蓋左下角的3號(hào)子棋盤。9/21/202325計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋的算法voiceCoverBoard(n,tr,Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方格(dr,dc)落在那個(gè)子棋盤：⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位置。9/21/202326計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：tr是0區(qū)和1區(qū)的首行，tc是0區(qū)和3區(qū)的首列;tr+s是3區(qū)和2區(qū)的首行;tc+s是1區(qū)和2區(qū)的首列0312trtcss9/21/202327計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：tr是0區(qū)和Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：0312trtcssjr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s–1;jc[1]=tc+s;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s;jc[3]=tc+s–1;jr[0]=tr+s–1;jc[0]=tc+s–1jr[1]=tr+s–1;jc[1]=tc+sjr[2]=tr+s;jc[2]=tc+sjr[3]=tr+s;jc[3]=tc+s–19/21/202328計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：0312trCoverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方格(dr,dc)落在那個(gè)子棋盤：我們可以依據(jù)結(jié)合部方格的行號(hào)和列號(hào)來判斷特殊方格落在哪個(gè)子棋盤中。0132trtcssjr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s;jc[1]=tc+s–1;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s–1;jc[3]=tc+s;9/21/202329計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方格(dr,dc)落在那個(gè)子棋盤：⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位置。if(dr<=jr[0]&&dc<=jc[0])r=0elseif(dr<=jr[1]&&dc>=jc[1])r=1elseif(dr>=jr[2]&&dc>=jc[2])r=2elseif(dr>=jr[3]&&dc<=jc[3])r=3;jr[0]=tr+s–1;jc[0]=tc+s–1;jr[1]=tr+s;jc[1]=tc+s–1;jr[2]=tr+s;jc[2]=tc+s;jr[3]=tr+s–1;jc[3]=tc+s;若特殊方格的行標(biāo)dr<=jr[0]且列標(biāo)dc<=jc[0]，則特殊方格位于在0號(hào)子棋盤中。其余類似。r指明了這點(diǎn)。9/21/202330計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑴計(jì)算結(jié)合部方格位置：⑵判斷特殊方Coverjoin的實(shí)現(xiàn)⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位置：if(r=0){sr[0]=dr;sc[0]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=1,2,3}elseif(r=1){sr[1]=dr;sc[1]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,2,3}elseif(r=2){sr[2]=dr;sc[2]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,1,3}elseif(r=3){sr[1]=dr;sc[1]=dc;Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];k=0,1,2};注意：此處由于幻燈片篇幅的原因，簡寫成這樣，實(shí)際表示對(duì)于k=1,2,3，執(zhí)行{Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]];}，即覆蓋相應(yīng)格子，并將其作為對(duì)應(yīng)子棋盤的特殊方格。下面亦如此。9/21/202331計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位Coverjoin的實(shí)現(xiàn)⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位置也可以用如下的語句來實(shí)現(xiàn)：sr[r]=dr;sc[r]=dc;for(k=0,k<4,i++)if(k<>r){Board[jr[k]][jc[k]]=tile;sr[k]=jr[k];sc[k]=jc[k]]};特殊子棋盤的特殊方格還是原來的。對(duì)每個(gè)非特殊子棋盤，則覆蓋其結(jié)合部的方格并將其作為該子棋盤的特殊方格。由于這個(gè)操作可以用此簡單表示，所以才在上一張幻燈片上采用了簡記的方式。9/21/202332計(jì)算計(jì)算法設(shè)計(jì)與分析Coverjoin的實(shí)現(xiàn)⑶覆蓋結(jié)合部并確定各子棋盤特殊方格位棋盤覆蓋算法的主程序main(intn,intdr,intdc){ints=2nintBoard[s][s]=0;inttile=0;CoverBoard(n,0,0,dr,dc);}請(qǐng)同學(xué)們自己編程來具體實(shí)現(xiàn)這個(gè)程序。9/21/202333計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法的主程序main(intn,intdr,棋盤覆蓋算法的正確性要證明一個(gè)算法的正確性，需要證明兩點(diǎn)：(1)算法的部分正確性；(2)算法的終止性。下面我們用歸納法證明棋盤覆蓋算法的部分正確性：9/21/202334計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法的正確性要證明一個(gè)算法的正確性，需要證明兩點(diǎn)：8棋盤覆蓋算法的部分正確性歸納基礎(chǔ)：k=0時(shí)，特殊棋盤僅含一個(gè)特殊方格，顯然已經(jīng)正確覆蓋。假設(shè)對(duì)2k–1的特殊棋盤均可正確覆蓋。對(duì)2k的特殊棋盤，算法劃分為四個(gè)2k–1的子棋盤。用一塊L型骨牌覆蓋三個(gè)正常子棋盤的結(jié)合處后，恰形成四個(gè)2k–1的特殊棋盤。由歸納假設(shè)，它們均可被正確覆蓋。因而也正確覆蓋了2k的特殊棋盤。由歸納法可知，棋盤覆蓋算法是部分正確。9/21/202335計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法的部分正確性歸納基礎(chǔ)：k=0時(shí)，特殊棋盤僅含棋盤覆蓋算法的終止性算法的終止性：遞歸終止條件為遞歸元size為1時(shí)遞歸終止。遞歸元size的初值為2k。每次遞歸時(shí)遞歸元減半，即size=size/2；因此，必然在有窮步內(nèi)遞減為1。所以此算法必定終止。由部分正確性和終止性可知，此算法是完全正確的。9/21/202336計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法的終止性算法的終止性：由部分正確性和終止性可知，棋盤覆蓋算法的復(fù)雜性設(shè)T(k)是棋盤覆蓋算法覆蓋2k×2k的棋盤所需要的時(shí)間，則T(k)滿足如下遞歸方程：T(k)=O(1)k=04T(k–1)+O(1)k＞0遞歸元遞減方式是減法，故此分治法實(shí)質(zhì)是遞推關(guān)系。由a=4可知T(k)=O(4k)。覆蓋2k×2k的棋盤要用(4k–1)/3個(gè)L型骨牌，故此算法是一個(gè)在漸進(jìn)意義下最優(yōu)的算法。9/21/202337計(jì)算計(jì)算法設(shè)計(jì)與分析棋盤覆蓋算法的復(fù)雜性設(shè)T(k)是棋盤覆蓋算法覆蓋2k×2k的小結(jié)用減法方式遞減的遞歸式按其遞歸元形成一個(gè)遞推序列。遞推關(guān)系的遞歸程序的時(shí)間復(fù)雜性T(n)通常不小于

O(an)，這里a是子問題的個(gè)數(shù)。用遞推遞歸求解的思路仍是先考慮最簡情況，再考慮復(fù)雜情況與較簡情況關(guān)系。程序的完全正確性由其部分正確性和終止性兩部分構(gòu)成。9/21/202338計(jì)算計(jì)算法設(shè)計(jì)與分析小結(jié)用減法方式遞減的遞歸式按其遞歸元形成一個(gè)遞推序列。8/6通信信道上允許傳輸?shù)膯卧~已知在通信信道上傳輸?shù)膯卧~只能由a、b和c三個(gè)字母組成并且其中不得有兩個(gè)字母a連續(xù)出現(xiàn)。請(qǐng)編寫一個(gè)程序生成所有在通信信道上允許傳輸?shù)拈L度為n的單詞。將這樣的單詞稱為長度為n的合法單詞。我們?cè)撊绾蝸砜紤]編寫這個(gè)程序呢？1、先分析最簡單情況的解。2、再分析復(fù)雜情況如何由較簡情況組成。9/21/202339計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~已知在通信信道上傳輸?shù)膯卧~只能由a、通信信道上允許傳輸?shù)膯卧~應(yīng)該是長度n=1的單詞。此問題中最簡單的情況是什么？長度為1的合法單詞只有三個(gè)，即a、b和c。下面我們?cè)倏紤]長度為n(n>1)的合法單詞是如何由長度n–1的合法單詞構(gòu)成的。9/21/202340計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~應(yīng)該是長度n=1的單詞。此問題中通信信道上允許傳輸?shù)膯卧~把長度為n合法單詞w去掉最前面的一個(gè)符號(hào)后所剩下的就是長度為n–1的單詞w’。顯然w’仍然應(yīng)該是合法單詞。如何考慮用長度n–1的合法單詞來構(gòu)成長度n的合法單詞呢？于是有：w=a+w’b+w’c+w’這里用符號(hào)+表示符號(hào)串的連接運(yùn)算。9/21/202341計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~把長度為n合法單詞w去掉最前面的一通信信道上允許傳輸?shù)膯卧~先考慮w=a+w’的情況：于是有：w=a+b+w’’a+c+w’’因?yàn)橥ㄐ判诺郎系暮戏▎卧~中不允許出現(xiàn)連續(xù)的a，所以w’只能以b或者c開頭。于是w’=b+w’’或者w’=c+w’’。這里w’’為任意的長度為n–2的合法單詞。將長度為n的合法單詞命名為Legal(n)。9/21/202342計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~先考慮w=a+w’的情況：于通信信道上允許傳輸?shù)膯卧~先考慮w=a+w’的情況：于是有：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)

因?yàn)橥ㄐ判诺郎系暮戏▎卧~中不允許出現(xiàn)連續(xù)的a，所以w’只能以b或者c開頭。于是w’=b+w’’或者w’=c+w’’。這里w’’為任意的長度為n–2的合法單詞。9/21/202343計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~先考慮w=a+w’的情況：于通信信道上允許傳輸?shù)膯卧~再考慮w=b+w’和w=c+w’的情況：于是有：Legal(n)=b+Legal(n–1)

c+Legal(n–1)

這里的w’可以為任意的長度為n–1的合法單詞。9/21/202344計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~再考慮w=b+w’和w=通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關(guān)系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

現(xiàn)在發(fā)生了一個(gè)新的情況！什么情況？9/21/202345計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關(guān)系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

這是個(gè)兩步遞歸！可是我們只考慮了n=1這一種最簡單情況！要增加n=0的情況。9/21/202346計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與長度較短的合法單詞之間有如下的關(guān)系：Legal(n)=a+b+Legal(n–2)

a+c+Legal(n–2)b+Legal(n–1)

c+Legal(n–1)

我們令當(dāng)n=0時(shí)的合法單詞為空串

，即Legal(0)=

。9/21/202347計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~綜合起來可以得到長度為n的合法單詞與通信信道上允許傳輸?shù)膯卧~綜合n為0和1的最簡單情況后，有：Legal(n)=

n=0bn=1cn=1an=1a+b+Legal(n–2)n>1a+c+Legal(n–2)n>1b+Legal(n–1)n>1c+Legal(n–1)n>19/21/202348計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~綜合n為0和1的最簡單情況后，有程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打印出所有在通信信道上傳輸?shù)拈L度為n的合法單詞。現(xiàn)在你頭腦里想象的打印過程該是什么樣子的呢？9/21/202349計(jì)算計(jì)算法設(shè)計(jì)與分析程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打印出所有在通信信道上傳輸?shù)拈L度為n的合法單詞。我想：這個(gè)程序應(yīng)該是從左向右逐個(gè)符號(hào)地生成每一個(gè)長度為n的合法單詞。每生成一個(gè)合法單詞，就把它打印出去。9/21/202350計(jì)算計(jì)算法設(shè)計(jì)與分析程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打印出所有在通信信道上傳輸?shù)拈L度為n的合法單詞。我想：那么，這個(gè)程序就應(yīng)該有個(gè)存放這個(gè)長度為n的合法單詞的變量，就叫它w[n]。干脆把這個(gè)程序叫做Legal(w,n)好了。9/21/202351計(jì)算計(jì)算法設(shè)計(jì)與分析程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打印出所有在通信信道上傳輸?shù)拈L度為n的合法單詞。我想：那么，什么時(shí)候就該打印合法單詞w[n]呢？…………那不就是n=0的時(shí)候嗎？……9/21/202352計(jì)算計(jì)算法設(shè)計(jì)與分析程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打印出所有在通信信道上傳輸?shù)拈L度為n的合法單詞。aha!Igotit!按照遞歸規(guī)則，從n開始，就是從左至右，將合法的符號(hào)放進(jìn)w；每放一個(gè)符號(hào)，n就減一。當(dāng)n個(gè)符號(hào)全都放進(jìn)去了，就是n=0了，就把w打印出去。9/21/202353計(jì)算計(jì)算法設(shè)計(jì)與分析程序設(shè)計(jì)的思考現(xiàn)在就讓我們來設(shè)計(jì)這個(gè)程序吧！這個(gè)程序要打打印合法單詞的程序Legal(w[n],intk){if(k=0){printw}elseif(k=1){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(intn){intw[n]=0;Legal(w[n],n)}考慮運(yùn)算w+x。9/21/202354計(jì)算計(jì)算法設(shè)計(jì)與分析打印合法單詞的程序Legal(w[n],intk){考打印合法單詞的程序Legal(w[n],intk){if(k=0){printw}elseif(k=1){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(intn){intw[n]=0;Legal(w[n],n)}w+x就是w[n–k]=x。w+x+y就是w[n–k]=x;w[n–k+1]=y。9/21/202355計(jì)算計(jì)算法設(shè)計(jì)與分析打印合法單詞的程序Legal(w[n],intk){w打印合法單詞的程序我們讓遞歸元的初值為0，終止值為n，而遞歸元的遞減方式改成加法，即n+1。于是這個(gè)程序還可改寫成下面的樣子：考慮到運(yùn)算w+x的方便我們可以改變遞歸的方向。9/21/202356計(jì)算計(jì)算法設(shè)計(jì)與分析打印合法單詞的程序我們讓遞歸元的初值為0，終止值為n，而遞歸打印合法單詞的程序Legal(w[n],intk){if(k=n){printw}elseif(k=n–1){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(intn){intw[n]=0;Legal(w[n],0)}k=n時(shí)遞歸終止。遞歸元用加法來遞減。直接將數(shù)組w的第k個(gè)分量賦值為a。遞歸元的初值賦為0。請(qǐng)同學(xué)們自己變成來具體實(shí)現(xiàn)這個(gè)程序。9/21/202357計(jì)算計(jì)算法設(shè)計(jì)與分析打印合法單詞的程序Legal(w[n],intk){k算法的時(shí)間復(fù)雜性這個(gè)算法是一個(gè)遞推的遞歸式，并且是一個(gè)兩步遞歸。由前面的基本分析可以斷定其復(fù)雜性應(yīng)該是指數(shù)的，即T(n)=O(an)。這個(gè)算法中的子任務(wù)為2，因此它的時(shí)間復(fù)雜性應(yīng)該不會(huì)低于O(2n)。O((1+√3)n)。這個(gè)程序的時(shí)間復(fù)雜性是它的復(fù)雜性實(shí)際上決定于合法單詞的數(shù)量。9/21/202358計(jì)算計(jì)算法設(shè)計(jì)與分析算法的時(shí)間復(fù)雜性這個(gè)算法是一個(gè)遞推的遞歸式，并且是一個(gè)兩步遞通信信道上允許傳輸?shù)膯卧~計(jì)算通信信道上允許傳輸?shù)暮戏▎卧~個(gè)數(shù)。解：令h(n)為的長度≤n的合法單詞個(gè)數(shù)。由前面的討論我們有：最簡單情況時(shí)h(0)=1，h(1)=3。當(dāng)n≥2時(shí)：h(n)=2h(n–1)+2h(n–2)求解這個(gè)遞歸方程可得：(2+√3)2√3(1+√3)n+h(n)=(–2+√3)2√3(1–√3)n這個(gè)遞歸函數(shù)也是著名的斐波拉契函數(shù)。有趣的是，對(duì)于任意的n，這個(gè)無理式的結(jié)果都是整數(shù)。9/21/202359計(jì)算計(jì)算法設(shè)計(jì)與分析通信信道上允許傳輸?shù)膯卧~計(jì)算通信信道上允許傳輸