算法設(shè)計(jì)與分析耿國(guó)華第二章

第二章遞歸與分治策略算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析耿國(guó)華本章內(nèi)容2.1遞歸的概念2.2具有遞歸特性的問(wèn)題2.3遞歸過(guò)程的設(shè)計(jì)與設(shè)計(jì)2.4遞歸算法分析2.4.1替換法2.4.2遞歸樹法2.4.3主方法2.5分治法的基本思想2.6分治法的適用條件2.7分治法的基本步驟2.8分治法典型示例2.8.1n個(gè)數(shù)中求出最大/最小值2.8.2快速排序2.8.3大整數(shù)乘法2.8.4折半查找2.8.5

矩陣乘法小結(jié)

Chapter22遞歸與分治策略當(dāng)計(jì)算機(jī)求解的問(wèn)題規(guī)模較大，直接解決困難甚至根本沒(méi)辦法直接求解時(shí)，往往會(huì)考慮能否將該問(wèn)題分割成幾個(gè)具有同等性質(zhì)的子問(wèn)題，將問(wèn)題規(guī)模減小后完成求解過(guò)程。例如，對(duì)于n個(gè)數(shù)的排序問(wèn)題，當(dāng)n為1時(shí)，不需要進(jìn)行任何比較運(yùn)算，當(dāng)n=2時(shí)，僅需進(jìn)行一次比較運(yùn)算即可，當(dāng)n為3時(shí)，需要進(jìn)行兩次比較，依此類推。當(dāng)n比較大時(shí)，這樣的排序方式就比較難以處理，程序運(yùn)行的效率會(huì)很低。諸如此類的大規(guī)模問(wèn)題，往往會(huì)考慮能否將該問(wèn)題分割成幾個(gè)具有同等性質(zhì)的子問(wèn)題，將問(wèn)題規(guī)模減小后完成求解過(guò)程。

Chapter22遞歸與分治策略基于這種指導(dǎo)思想，引出了分治法。由于分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易求解。由于分治后的子問(wèn)題與原問(wèn)題的類型一致，因此，在分治法中經(jīng)常使用遞歸技術(shù)求解問(wèn)題，遞歸與分治兩者之間是相輔相成的。

Chapter22.1遞歸概念

在定義自身的同時(shí)，出現(xiàn)對(duì)自身的直接或間接調(diào)用（自己調(diào)用自己）。一個(gè)直接或間接調(diào)用自己的算法稱為遞歸算法。

Chapter22.1遞歸概念遞歸算法的特點(diǎn)（1）描述簡(jiǎn)捷；（2）結(jié)構(gòu)清晰；（3）算法的正確性比較容易證明。Chapter22.1遞歸概念遞歸轉(zhuǎn)為非遞歸的原因（1）遞歸的執(zhí)行效率低；（2）空間消耗多；（3）軟、硬件環(huán)境條件限制；

Chapter22.1遞歸概念寫遞歸注意問(wèn)題（1）算法中的過(guò)程或函數(shù)對(duì)自身進(jìn)行調(diào)用；（2）遞歸控制條件；有一個(gè)明確的遞歸結(jié)束條件，即遞歸出口；（3）非遞歸的初始值的定義。Chapter22.1遞歸概念遞歸設(shè)計(jì)方法（1）尋找分解方法；（2）設(shè)計(jì)遞歸出口（尋找所分解的問(wèn)題的出口）。Chapter22.1遞歸概念遞歸算法的執(zhí)行過(guò)程中包括兩個(gè)執(zhí)行階段（1）自上而下的遞歸進(jìn)層階段（遞推階段）（2）自下而上的出層階段（回歸階段）Chapter22.2具有遞歸特性的問(wèn)題（1）遞歸定義的數(shù)學(xué)函數(shù)例2-1遞歸定義的Ackerman函數(shù)：Chapter22.2具有遞歸特性的問(wèn)題

上述Ackerman函數(shù)的算法描述如下：

procedureintack(m,n) ifm=0then returnn+1; elseifn==0then returnack(m-1,1); elsereturnack(m-1,ack(m,n-1)); endif endackChapter22.2具有遞歸特性的問(wèn)題例2-2：遞歸定義的斐波那契(Fibonacci)序列。 無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，……可定義為斐波那契數(shù)列。遞歸形式為Chapter22.2具有遞歸特性的問(wèn)題

根據(jù)函數(shù)的遞歸定義，可以直接設(shè)計(jì)算法2.2求解斐波那契過(guò)程F(n)如下，

procedureF(n) ifn≤1then return1 else returnF(n-1)+F(n-2)endif endFChapter22.2具有遞歸特性的問(wèn)題Chapter2圖2-1斐波那契算法的遞歸結(jié)構(gòu)(n=6)2.2具有遞歸特性的問(wèn)題（2）遞歸定義的數(shù)據(jù)結(jié)構(gòu)

在數(shù)據(jù)結(jié)構(gòu)中，如廣義表、二叉樹、樹等結(jié)構(gòu)其本身均具有固有的遞歸特性，可以自然地采用遞歸法進(jìn)行處理。（3）遞歸求解方法

許多問(wèn)題的求解過(guò)程可以用遞歸分解的方法描述，例如：計(jì)算兩非負(fù)整數(shù)最大公約數(shù)的歐幾里得算法和著名的漢諾塔問(wèn)題（Hanoi）問(wèn)題。

Chapter22.2具有遞歸特性的問(wèn)題例2-3：歐幾里得(Euclid)算法。

已知兩個(gè)非負(fù)整數(shù)a和b，且a＞b≥0，求這兩個(gè)數(shù)的最大公因數(shù)。 輾轉(zhuǎn)相除法：若b=0，則a和b的最大公因數(shù)等于a；若b＞0，則a和b的最大公因數(shù)等于b和用b除a的余數(shù)的最大公因數(shù)。當(dāng)a=22，b=8時(shí)，遞歸結(jié)構(gòu)如圖2-2所示。Chapter22.2具有遞歸特性的問(wèn)題Chapter2根據(jù)輾轉(zhuǎn)相除法的遞歸定義算法2.2用遞歸解決兩個(gè)數(shù)的最大公因數(shù)procedureGCD(a,b)

//約定a>bifb=0thenreturn

aelsereturn

GCD(b,amodb)endifendGCD圖2-2

當(dāng)a=22，b=8時(shí)，輾轉(zhuǎn)相除法遞歸結(jié)構(gòu)(n=6)2.2具有遞歸特性的問(wèn)題例2.4漢諾塔(Hanoi)問(wèn)題。

現(xiàn)在有三根柱子，標(biāo)號(hào)為X,Y,Z，X柱子上從下到上按金字塔狀疊放著n個(gè)不同大小的圓盤，現(xiàn)在把所有盤子一個(gè)一個(gè)移動(dòng)到柱子Z上，并且每次移動(dòng)同一根柱子上都不能出現(xiàn)大盤子在小盤子上方，請(qǐng)問(wèn)至少需要多少次移動(dòng)，設(shè)移動(dòng)次數(shù)為H(n)。

Chapter22.2具有遞歸特性的問(wèn)題例2.4漢諾塔(Hanoi)問(wèn)題。

分析：當(dāng)n很大時(shí)這個(gè)問(wèn)題不好解決，我們可以使用遞歸技術(shù)來(lái)解決該問(wèn)題 當(dāng)n=1時(shí)，將編號(hào)為1的圓盤從X柱子直接移到柱子Z上。 當(dāng)n>1時(shí)，需要利用柱子Y作為輔助柱子，設(shè)法將n-1個(gè)較小的盤子按規(guī)則移到柱子Y中，然后將編號(hào)為n的盤子從X柱子移到Z柱子，最后將n-1個(gè)較小的盤子移到Z柱子中。Chapter22.2具有遞歸特性的問(wèn)題例2.4漢諾塔(Hanoi)問(wèn)題。

算法2.4用遞歸解決規(guī)模為n的Hanoi塔問(wèn)題

VoidHANOI(n，X，Y，Z) { ifn=1 MOVE(X，1，Z) else{ HANOI(n-1，X，Z，Y) MOVE(X，n，Z) HANOI(n-1，Y，X，Z) } }Chapter22.2具有遞歸特性的問(wèn)題

下面給出三個(gè)盤子搬動(dòng)時(shí)HANOI(3,A,B,C)的遞歸調(diào)用過(guò)程，如圖2-3所示HANOI(3,A,B,C)HANOI(2,A,C,B):HANOI(1,A,B,C) MOVE(A->C)1號(hào)搬到CMOVE(A->B)2號(hào)搬到BHANOI(1,C,A,B) MOVE(C->B)1號(hào)搬回到BMOVE(A->C)3號(hào)搬到CHANOI(2,B,A,C):HANOI(1,B,C,A) MOVE(B->A)1號(hào)搬到AMOVE(B->C)2號(hào)搬到CHANOI(1,A,B,C) MOVE(A->C)1號(hào)搬到CChapter22.2具有遞歸特性的問(wèn)題Chapter2圖2-3漢諾塔的執(zhí)行過(guò)程(n=3)2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2

在算法的遞歸調(diào)用過(guò)程中,進(jìn)行遞歸進(jìn)層（i→i+1層）系統(tǒng)需要做三件事：⑴保留本層參數(shù)與返回地址；⑵為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)，給下層參數(shù)賦值；⑶將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，遞歸退層（i←i+1層）系統(tǒng)也應(yīng)完成三件工作：⑴保存被調(diào)函數(shù)的計(jì)算結(jié)果；⑵釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)，恢復(fù)上層參數(shù)；⑶依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2

當(dāng)遞歸函數(shù)調(diào)用時(shí)，應(yīng)按照“后調(diào)用先返回”的原則處理調(diào)用過(guò)程，因此上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過(guò)棧來(lái)實(shí)現(xiàn)。系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，而每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)。顯然，當(dāng)前正在運(yùn)行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂。2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2例2.5n階乘的遞歸算法和遞歸調(diào)用過(guò)程（0為最小規(guī)模）

（(n-1)比n的規(guī)模更?。┢溥f歸算法如下：intf(intn)/*設(shè)n>=0*/{ if(n==0)return(1); elsereturn(n*f(n-1));}2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2圖2-4f(3)遞歸調(diào)用示意圖2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2遞歸進(jìn)層3件事：保存本層參數(shù)、返回地址分配局部數(shù)據(jù)空間，傳遞參數(shù)轉(zhuǎn)第一條指令遞歸退層3件事：恢復(fù)上層傳遞結(jié)果轉(zhuǎn)斷點(diǎn)執(zhí)行2.3遞歸過(guò)程的設(shè)計(jì)與實(shí)現(xiàn)Chapter2 f(3)3x2

f(2)2x1自上而下自下而上遞

歸進(jìn)層階段f(1)1x1返回階段 f(0)1×1圖2-5f(3)遞歸調(diào)用流程變化示意圖2.4遞歸算法分析2.4.1替換法2.4.2遞歸樹法2.4.3主方法Chapter22.4遞歸算法分析Chapter2遞歸方程的求解一般可采用如下三種方法：

（1）替換法(SubstitutionMethod)（2）遞歸樹法(RecursionMethod)（3）主方法(MasterMethod).當(dāng)一個(gè)算法包含對(duì)自身的遞歸調(diào)用過(guò)程時(shí)，該算法的運(yùn)行時(shí)間復(fù)雜度可用遞歸方程進(jìn)行描述，求解該遞歸方程，可得到對(duì)該算法時(shí)間復(fù)雜度的函數(shù)度量。2.4.1替換方法Chapter2(1)替換方法替換方法的最簡(jiǎn)單方式為：根據(jù)遞歸規(guī)律，將遞歸公式通過(guò)方程展開、反復(fù)代換子問(wèn)題的規(guī)模變量，通過(guò)多項(xiàng)式整理，如此類推，從而得到遞歸方程的解。2.4.1替換方法Chapter2例2.6漢諾塔算法（見例2.5）的時(shí)間復(fù)雜度分析。假設(shè)漢諾塔算法的時(shí)間復(fù)雜度為T(n)，例2.5的算法遞歸方程為：2.4.1替換方法Chapter2利用替換法求解該方程：得到該算法的時(shí)間復(fù)雜度2.4.1替換方法Chapter2

例2.72-路歸并排序的遞歸算法分析。假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到個(gè)長(zhǎng)度為2（n為奇數(shù)時(shí)，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列；在此基礎(chǔ)上，再對(duì)長(zhǎng)度為2的有序子序列進(jìn)行兩兩歸并，得到若干個(gè)長(zhǎng)度為4的有序子序列；如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法被稱作2-路歸并排序。2.4.1替換方法Chapter2兩有序子序列合并為一個(gè)有序序列2-路歸并排序法的基本操作是將待排序列中相鄰的兩個(gè)有序子序列合并成一個(gè)有序序列,算法如下：voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper2[]) /*已知r1[low..mid]和r1[mid+1..high]分別按關(guān)鍵字有序排列，將它們合并成一個(gè)有序序列，存放在r2[low..high]*/ {i=low；j=mid+1；k=low；while((i<=mid)&&(j<=high)) { if(r1[i].key<=r1[j].key) { r2[k]=r1[i]；++i；} else { r2[k]=r1[j]；++j；} ++k； } while(i<=mid) {r2[k]=r1[i];k++,i++;} while(j<=high)； {r2[k]=r1[j];k++;j++;}}/*Merge*/2.4.1替換方法Chapter2在合并過(guò)程中，兩個(gè)有序的子表被遍歷了一遍，表中的每一項(xiàng)均被復(fù)制了一次。因此，合并的代價(jià)與兩個(gè)有序子表的長(zhǎng)度之和成正比，該算法的時(shí)間復(fù)雜度為O(n)。2-路歸并排序的遞歸方法實(shí)現(xiàn)算法思想：將r1[]中的記錄用歸并法排序后放到r3[]中，可以分為下面三個(gè)步驟：①將r1[]前半段的記錄用歸并法排序后放到r2[]的前半段中；②將r1[]后半段的記錄用歸并法排序后放到r2[]的后半段中；③將r2[]的前半段和后半段合并到r3[]中。2.4.1替換方法Chapter22-路歸并排序的完整算法如下：voidMSort(RecordTyper1[],intlow,inthigh,RecordTyper3[])/*r1[low….high]排序后放在r3[low….high]中，r2[low….high]為輔助空間*/{RecordType*r2； r2=(RecordType*)malloc(sizeof(RecordType)*(hight–low+1)); if(low==high)r3[low]=r1[low]； else{ mid=(low+high)/2；MSort(r1，low，mid,r2)；MSort(r1，mid+1，high,r2)；Merge(r2，low，mid，high，r3)； } free(r2);}/*MSort*/2.4.1替換方法Chapter2二路歸并排序算法的遞歸方程為：當(dāng)n>1時(shí)，利用替換法，可得：2.4.1替換方法Chapter2取則（當(dāng)n為奇數(shù)時(shí)，即可用替代）從而，即二次歸并排序的算法時(shí)間復(fù)雜度為可將上述遞歸方程推廣至一般形式，可記為：2.4.1替換方法Chapter2對(duì)該方程通過(guò)替換法求解：由可得到解一般形式為：2.4.1替換方法Chapter2若那么存在整數(shù)k，使有從而，當(dāng)d(n)為常數(shù)時(shí)，有：當(dāng)，c為常數(shù)時(shí)，有：即該遞歸方程的解為：其中2.4.1替換方法Chapter2推論：證明：①當(dāng)時(shí)，，收斂，②當(dāng)時(shí)，有所以③當(dāng)時(shí)，則2.4.1替換方法Chapter2所以，

在上述二路歸并算法的遞歸方程中，有利用推論公式②可直接得到算法的時(shí)間復(fù)雜度為。

替換方法求解遞歸方程還可以通過(guò)如下步驟進(jìn)行：（1）猜測(cè)界限函數(shù)（2）對(duì)猜測(cè)進(jìn)行證明，并尋找到猜測(cè)中常量C的范圍。2.4.1替換方法Chapter2例2.8

利用替換方法解遞歸方程假設(shè)上界函數(shù)為O(nlog2n)，假設(shè)該上界函數(shù)對(duì)于[n/2]是成立的，也就是說(shuō)存在常數(shù)c,有T(n/2)≤c(n/2)log2(n/2)成立?，F(xiàn)在需要證明T(n)≤cnlog2n。根據(jù)猜測(cè)，有：當(dāng)c≥1時(shí),上述結(jié)果成立下面證明猜測(cè)對(duì)于邊界條件成立，即證明對(duì)于選擇的常數(shù)c，對(duì)于邊界條件成立。2.4.1替換方法Chapter2

假設(shè)T(1)=1是遞歸方程的惟一邊界條件，那么對(duì)于 與發(fā)生矛盾。因此，歸納法中的歸納基礎(chǔ)不成立。所以T(1)=1不能作為邊界條件。由遞歸方程T(2)=2T(1)+2;T(3)=2T(1)+3;得T(2)和T(3)均依賴T(1),選擇T(2)和T(3)作為歸納證明中的邊界條件。由遞歸方程可得T(2)=4和T(3)=5算法復(fù)雜度的漸近表示法只要求對(duì)n≥n0，成立，因此可設(shè)n0=2，當(dāng)n≥2時(shí)，成立。再選擇c≥2，就會(huì)使得 和成立。以下對(duì)此進(jìn)行證明：2.4.1替換方法Chapter2

當(dāng)n=2k時(shí)，上式可寫為T(n)=nT(1)+nlog2n,若n=2k-1,則上式展開時(shí)用T((n+1)/2)+T((n-1)/2)替代2T(n/2)，用(n+1)/2+(n-1)/2代替n，同樣可得到T(n)=nT(1)+nlog2n。由遞歸公式，T(1)=1,則 T(n)=n+nlog2n=nlog22+nlog2n=nlog2(2n)當(dāng)n>=2時(shí)，要使得T(n)=nlog2(2n)<=cnlog2n則需 c>=log2(2n)/log2(n)當(dāng)n=2時(shí)，由上式c>=2即可當(dāng)n=3時(shí)，因log2(2n)/log2(n)=log2(6)/log2(3)<2，此時(shí)取c>=2滿足條件。2.4.1替換方法Chapter2

當(dāng)n>3時(shí)，此時(shí)取c>=2滿足條件。由以上證明，當(dāng)n>=2,c>=2時(shí)，成立。2.4.2遞歸樹方法Chapter2

遞歸樹的方法可以更好地猜測(cè)一個(gè)問(wèn)題的解，并用替換方法證明這個(gè)猜測(cè)。圖2-4表明了如何求解方程時(shí)構(gòu)造遞歸樹的方法，其中n假設(shè)假設(shè)為4的冪。圖2-4遞歸樹的構(gòu)造過(guò)程(2)遞歸樹方法2.4.2遞歸樹方法Chapter2

深度為i的結(jié)點(diǎn)，其子問(wèn)題的規(guī)模為n/4i,當(dāng)n/4i=1時(shí)，子問(wèn)題規(guī)模為1，這時(shí)位于樹的最后一層（即i=log4n）.在圖2-4的遞歸樹中，層數(shù)是從0開始算起的，第一層層數(shù)為0，最后一層的層數(shù)為log4n，共有l(wèi)og4n+1層。深度是從0開始算起的，第一層深度為0，最后一層深度為log4n，深度共為log4n+1。高度則是深度減1，為log4n。第i層的結(jié)點(diǎn)數(shù)為3i。(每一層的結(jié)點(diǎn)數(shù)是上一層結(jié)點(diǎn)數(shù)的三倍)層數(shù)為的每個(gè)結(jié)點(diǎn)的開銷為(每一層子問(wèn)題規(guī)模為上一層的1/4)2.4.2遞歸樹方法Chapter2第i層上結(jié)點(diǎn)的總開銷為層數(shù)為log4n的最后一層有個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的開銷為T(1)，該層總開銷即將所有層的開銷相加得到整棵樹的開銷：

2.4.2遞歸樹方法Chapter2現(xiàn)在利用替換方法證明我們的猜測(cè)是正確的。假設(shè)這個(gè)界限對(duì)于n/4成立，即存在某個(gè)常數(shù)d，代入遞歸方程可得根據(jù)上面式子，當(dāng)c≤(13/16)d時(shí)，有：2.4.3主方法Chapter2

主方法為我們提供了解如下形式遞歸方程的一般方法:其中a≥1，b>1為常數(shù)，f(n)是漸近正函數(shù)。算法將規(guī)模為n的問(wèn)題劃分成a個(gè)子問(wèn)題,每個(gè)子問(wèn)題的大小為n/b。求解這a個(gè)子問(wèn)題，每個(gè)所需時(shí)間為T(n/b)。函數(shù)f(n)表示劃分子問(wèn)題與組合子問(wèn)題解的開銷。(3)主方法2.4.3主方法Chapter2例2.9，對(duì)于遞歸方程雖然劃分后的子問(wèn)題(n/b)并不一定為整數(shù)，但用T(n/b)取代或?qū)f歸方程的漸近行為無(wú)影響，所以在表示這種遞歸函數(shù)時(shí)略去了向上取整和向下取整函數(shù)。2.4.3主方法Chapter2定理2.1設(shè)a≥1，b>1為常數(shù)，f(n)為一函數(shù)。T(n)由以下遞歸方程定義：其中n為非負(fù)整數(shù)，則T(n)有如下的漸近界限：

(1)若對(duì)某些常數(shù)ε>0，有那么(2)若那么(3)若對(duì)某些常數(shù)ε>0有且對(duì)常數(shù)c<1與所有足夠大的n，有那么2.4.3主方法Chapter2先來(lái)分析它的含義。在上述的每一種情況下，我們都把函數(shù)f(n)與函數(shù)進(jìn)行比較，遞歸方程的解由這兩個(gè)函數(shù)中較大的一個(gè)決定。第一種情形中，函數(shù)比函數(shù)f(n)更大，則解為：第二種情形中，這兩個(gè)函數(shù)一樣大，則解為：第三種情形中，f(n)是較大的函數(shù)，則解為:2.4.3主方法Chapter2我們還可以用圖2-5表示方程(2.1)，從另一個(gè)角度解釋主定理。圖2-5主定理的圖示2.4.3主方法Chapter2圖2-5所示樹中葉子結(jié)點(diǎn)數(shù)為：

對(duì)于第一種情形，從根到葉結(jié)點(diǎn)開銷的權(quán)重呈幾何級(jí)數(shù)增加。葉結(jié)點(diǎn)占有整個(gè)權(quán)重的恒定比例。

對(duì)于第二種情形，每一層的權(quán)重大致相同。對(duì)于第三種情形，從根到葉結(jié)點(diǎn)開銷的權(quán)重呈幾何級(jí)數(shù)減小2.4.3主方法Chapter2例2.10解遞歸方程解：由遞歸方程可得，a=4，b=2且f(n)=n。因此，選取,則

遞歸方程滿足主定理的第一種情形，因此2.5分治法的基本思想Chapter2

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。當(dāng)問(wèn)題規(guī)模n較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。2.5分治法的基本思想Chapter2

分治法的特點(diǎn)：（1）子問(wèn)題相互獨(dú)立且與原問(wèn)題形式相同；（2）反復(fù)分治，使劃分得到的小問(wèn)題小到不可再分 時(shí)，直接對(duì)其求解。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。2.6分治法的適用條件Chapter2

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：⑴該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；⑵該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。⑶利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；⑷該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。2.7分治法的基本步驟Chapter2

分治思想設(shè)計(jì)算法時(shí)一般包含的步驟

第一步，分解（割）。將待解決的問(wèn)題劃分成足夠小的問(wèn)題,相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；第二步，求解。若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題第三步，合并。自下而上，將子問(wèn)題的解逐層合并，得到原問(wèn)題的解。2.7分治法的基本步驟Chapter2

分治法的一般算法框架為：

divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問(wèn)題dividePintosmallersubinstancesP1,P2,...,Pk；//分解問(wèn)題for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問(wèn)題returnmerge(y1,...,yk);//將各子問(wèn)題的解合并為原問(wèn)題的解}2.7分治法的基本步驟Chapter2在對(duì)采用分法思想設(shè)計(jì)的算法進(jìn)行分析時(shí)，可用如下遞歸方程描述算法的運(yùn)行時(shí)間T(n)。在該遞歸方程中，如果問(wèn)題的規(guī)模足夠小(n≤c)，可以直接求解，則如果問(wèn)題規(guī)模n>c,還需被分解為k個(gè)規(guī)模大小為n/m的子問(wèn)題，且分析問(wèn)題與合并問(wèn)題解的時(shí)間分別為D(n)和C(n)，則對(duì)于該方程，設(shè)n為m的冪，記D(n)=C1(n)+C2(n)則該遞歸方程的解為：2.8分治法典型示例2.8.1n個(gè)數(shù)中求出最大/最小值2.8.2快速排序2.8.3大整數(shù)乘法2.8.4折半查找2.8.5矩陣乘法Chapter22.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2問(wèn)題描述：從給定的n個(gè)數(shù)中，設(shè)計(jì)算法在最壞情況下最多進(jìn)行用次比較，可找出給定n個(gè)數(shù)的最大和最小值。問(wèn)題分析：方法一：從n個(gè)數(shù)中找最大最小數(shù)可以通過(guò)如下過(guò)程進(jìn)行：第一步，通過(guò)n-1次比較找出最大值；第二步，從其余的n-1個(gè)數(shù)中通過(guò)n-2次比較找出最小值。這種常規(guī)的方法一共要進(jìn)行2n-3次比較((n-1)+(n-2))。要完成

2.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2

方法二：題目設(shè)計(jì)要求,可通過(guò)分治思想進(jìn)行算法設(shè)計(jì)。記n個(gè)數(shù)的集合為S,將其平分為元素個(gè)數(shù)為n/2的兩個(gè)集合S1,S2，。首先，分別在S1、S2中找出最大、最小值，分別記作MaxS1,MinS1,MaxS2,MaxS1；之后，通過(guò)2次比較，從所找到的該四個(gè)數(shù)中找出S中的最大、最小值,。從S1，S2中分別找出最大、最小值的方法可以按以上思想遞歸進(jìn)行。 2.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2根據(jù)上述分析，采用分治遞歸思想設(shè)計(jì)的算法如下：VoidSearchMaxMin(S){if(|S|==2)return(max(a,b),min(a,b)) else{S分成S1,S2 (max1,min1)=SearchMaxMin(S1)//找出S1中最大、最小值

(max2,min2)=SearchMaxMin(s2)//找出S2中最大、最小值

return(max(max1,max2),min(min1,min2))//找出S中最大、最小值

} } 2.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2以下對(duì)該遞歸算法進(jìn)行分析：(1).列出算法的遞歸方程。大小為n/2的2個(gè)集合分別遞歸比較（即2T(n/2)），所得分屬2個(gè)集合的最大和最小值之間需再進(jìn)行1次比較（即2次）。2.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2(2).求解遞歸方程。當(dāng)n>2時(shí)令n=2k，則因?yàn)樗?，從?.8.1分治舉例——n個(gè)數(shù)中求出最大最小值Chapter2(3).用數(shù)學(xué)歸納法證明是遞歸方程的解。當(dāng)n=2時(shí)，T(2)=1=當(dāng)n=2k時(shí)，若T(n)滿足

當(dāng)n=2k+1，時(shí)命題得證。由上例總結(jié)遞歸算法分析的三個(gè)步驟如下：首先，根據(jù)給出的遞歸算法列出遞歸方程；其次，推導(dǎo)求解遞歸方程；最后，證明所得到的解就是該遞歸方程的解。2.8.2分治舉例——快速排序Chapter2問(wèn)題描述：對(duì)給定的n個(gè)記錄A［p..r］進(jìn)行排序。問(wèn)題分析：基于分治設(shè)計(jì)的思想，從待排序記錄序列中選取一個(gè)記錄（通常選取第一個(gè)記錄）為樞軸，其關(guān)鍵字設(shè)為K1，然后將其余關(guān)鍵字小于K1的記錄移到前面，而將關(guān)鍵字大于K1的記錄移到后面，結(jié)果將待排序記錄序列分成兩個(gè)子表，最后將關(guān)鍵字為K1的記錄插到其分界線的位置處。我們將這個(gè)過(guò)程稱作一趟快速排序。2.8.2分治舉例——快速排序Chapter2通過(guò)一次劃分后，就以關(guān)鍵字為K1的記錄為界，將待排序序列分成了兩個(gè)子表，且前面子表中所有記錄的關(guān)鍵字均不大于K1，而后面子表中的所有記錄的關(guān)鍵字均不小于K1。對(duì)分割后的子表繼續(xù)按上述原則進(jìn)行分割，直到所有子表的表長(zhǎng)不超過(guò)1為止，此時(shí)待排序記錄序列就變成了一個(gè)有序表。具體的排序過(guò)程由以下三步組成：2.8.2分治舉例——快速排序Chapter2

(1)劃分：將數(shù)組A［p..r］劃分成兩個(gè)子數(shù)組A［p..q-1］和A［q+1..r］(其中之一可能為空)，滿足數(shù)組A［p..q-1］中的每個(gè)元素值不超過(guò)數(shù)組A［q+1..r］中的每個(gè)元素。計(jì)算下標(biāo)q作為劃分過(guò)程的一部分。

(2)解決：遞歸調(diào)用快速排序算法，對(duì)兩個(gè)子數(shù)組A［p..q-1］和A［q+1..r］進(jìn)行排序。

(3)合并：由于子數(shù)組中元素已被排序，無(wú)需合并操作，整個(gè)數(shù)組A［p..r］有序。

2.8.2分治舉例——快速排序Chapter2在該排序過(guò)程中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。2.8.2分治舉例——快速排序Chapter2根據(jù)上述思想設(shè)計(jì)的算法：template<classType>voidQuickSort(TypeA[],intp,intr){ifp<rthenq←PARTITION(A,p,r);QuickSort(A,p,q-1);//對(duì)左半段排序

QuickSort(A,q+1,r);//對(duì)右半段排序

endif}2.8.2分治舉例——快速排序Chapter2PARTITION(A,p,r)1x←A［p］//最最端元素作為樞軸元素2i←p-13forj←ptor-14doifA［j］≤x5theni←i+16exchangeA［i］A［j］7exchangeA［i+1］A［r］8returni+12.8.2分治舉例——快速排序Chapter2假設(shè)待劃分序列為A[left]，A[left+1]，…，A[right]，具體實(shí)現(xiàn)上述劃分過(guò)程時(shí)，可以設(shè)兩個(gè)指針i和j，它們的初值分別為left和right。首先將基準(zhǔn)記錄A[left]移至變量x中，使A[left]，即A[i]相當(dāng)于空單元，然后反復(fù)進(jìn)行如下兩個(gè)掃描過(guò)程，直到i和j相遇：j從右向左掃描，直到A[j].key<x.key時(shí)，將A[j]移至空單元A[i]，此時(shí)A[j]相當(dāng)于空單元。i從左向右掃描，直到A[i].key>x.key時(shí)，將A[i]移至空單元A[j]，此時(shí)A[i]相當(dāng)于空單元。2.8.2分治舉例——快速排序Chapter2

當(dāng)i和j相遇時(shí)，A[i]（或A[j]）相當(dāng)于空單元，且A[i]左邊所有記錄的關(guān)鍵字均不大于基準(zhǔn)記錄的關(guān)鍵字，而A[i]右邊所有記錄的關(guān)鍵字均不小于基準(zhǔn)記錄的關(guān)鍵字。最后將基準(zhǔn)記錄移至A[i]中，就完成了一次劃分過(guò)程。對(duì)于A[i]左邊的子表和A[i]右邊的子表可采用同樣的方法進(jìn)行進(jìn)一步劃分。圖2-6給出了一個(gè)表示第一次劃分過(guò)程的實(shí)例。2.8.2分治舉例——快速排序Chapter2

4862357755143598

x

4862357755143598low highlow62357755143598 highlow high35623577551498low high35623577551498low high35357755146298(a)一趟快速排序2.8.2分治舉例——快速排序Chapter2lowhigh35357755146298lowhigh35143577556298lowhigh3514357755629835143555776298lowhigh35143555776298lowhigh 3514354855776298lowhigh(a)一趟快速排序2.8.2分治舉例——快速排序Chapter2初始狀態(tài)：4862357755143598一次劃分后：{351435}48{55776298}分別進(jìn)行快速排序：{14}35{35}結(jié)束結(jié)束55{776298} {62}77{98}

結(jié)束結(jié)束(b)快速排序全過(guò)程

圖2-6快速排序過(guò)程示例2.8.2分治舉例——快速排序Chapter2快速排序最壞情況分析當(dāng)劃分過(guò)程產(chǎn)生的兩個(gè)子問(wèn)題規(guī)模分別為n-1和1時(shí)，快速排序出現(xiàn)最壞的情況。劃分的時(shí)間復(fù)雜度為O(n)。假設(shè)每次遞歸調(diào)用時(shí)產(chǎn)生這種不平衡的情況。間復(fù)雜度為Θ(n)，因?yàn)閷?duì)規(guī)模為0的數(shù)組的遞歸調(diào)用只會(huì)返回，(1)列出該算法最壞情況下的遞歸方程（2）求解遞歸方程當(dāng)n>1時(shí),2.8.2分治舉例——快速排序Chapter2即，在最壞情況下，該算法的時(shí)間復(fù)雜度為O(n2)。（3）證明n2是遞歸方程的解當(dāng)n=1時(shí)T(1)=1假設(shè)當(dāng)n=k時(shí)，當(dāng)n=k+1時(shí)，2.8.2分治舉例——快速排序Chapter2

即(k+1)2是遞歸方程的解。所以，n2是遞歸方程的解。因此，快速排序最壞情況下的運(yùn)行時(shí)間不比冒泡排序的運(yùn)行時(shí)間好，而最壞情況是在輸入已經(jīng)完全有序(升序)時(shí)出現(xiàn)的。2.8.2分治舉例——快速排序Chapter2快速排序最好情況分析在大多數(shù)均勻劃分的情況下,PARTITION產(chǎn)生兩個(gè)規(guī)模為n/2的子問(wèn)題，以下對(duì)該情況下的算法進(jìn)行分析。（1）列出遞歸方程（2）求解遞歸方程2.8.2分治舉例——快速排序Chapter2設(shè)n=2k,則

T(n)=n+nlog2n=O(nlog2n)

直接利用2.4節(jié)中的推論，也可得到該遞歸方程的解為T(n)=O(nlog2n)。也可以通過(guò)2.4節(jié)中的主方法進(jìn)行遞歸方程求解，遞歸方程符合主方法的第2種情形，可知該遞歸方程的解為T(n)=O(nlog2n)。2.8.2分治舉例——快速排序Chapter2（3）證明nlog2n是遞歸方程的解當(dāng)時(shí)假設(shè)時(shí)，成立則當(dāng)n>m時(shí)，不妨有：2.8.2分治舉例——快速排序Chapter2所以，nlog2n為遞歸方程的解。上述折半查找遞歸算法分析結(jié)果表明，如果劃分在算法的每一層遞歸上產(chǎn)生兩個(gè)相同規(guī)模的問(wèn)題，則得是快速排序算法的最佳情況。2.8.3分治舉例——大整數(shù)乘法Chapter2問(wèn)題描述：設(shè)有兩個(gè)n位二進(jìn)制數(shù)x，y，現(xiàn)要計(jì)算他們的乘積xy;問(wèn)題分析：兩個(gè)n位二進(jìn)制整數(shù)相乘，根據(jù)計(jì)算規(guī)則，兩個(gè)數(shù)中每位數(shù)都需要對(duì)應(yīng)做乘法運(yùn)算，因此，按照一般方法計(jì)算這兩個(gè)數(shù)乘法所需要的算法的復(fù)雜度是現(xiàn)采用分治思想進(jìn)行處理降低算法：設(shè)有兩個(gè)n位二進(jìn)制數(shù)x，y均為位。

其做了四次位的乘法，3次超過(guò)位的整數(shù)加法，運(yùn)算級(jí)別為2.8.3分治舉例——大整數(shù)乘法Chapter2(1)列出上述過(guò)程的遞歸方程(2)求解遞歸方程：當(dāng)n>1時(shí)，設(shè)n=2k,則k=log2n即，T(n)=O(n2)2.8.3分治舉例——大整數(shù)乘法Chapter2(3)證明n2是該遞歸方程的解當(dāng)時(shí)，假設(shè)時(shí)，成立則當(dāng)n>m時(shí)，不妨，有：2.8.3分治舉例——大整數(shù)乘法Chapter2從而,T(n)=O(n2)得證。在該算法中，通過(guò)分治法進(jìn)行了4次位的乘法運(yùn)算，但根據(jù)算法分析結(jié)果可知，并沒(méi)有改進(jìn)算法的性能，算法時(shí)間復(fù)雜度仍為O(n2)。該算法性能的提升，需要減少乘法算運(yùn)次數(shù)，可以通過(guò)以下方式進(jìn)行：先計(jì)算：，，則那么，在計(jì)算過(guò)程中，一共進(jìn)行了3次位的乘法運(yùn)算，6次加減法和2次移位。2.8.3分治舉例——大整數(shù)乘法Chapter2按上述改進(jìn)，得到大整數(shù)乘法的完整算法：longMULT(x,y,n){longs=SIGN(x)*SIGN(y);//計(jì)算結(jié)果符合

x=abs(x);y=abs(y);if(n==1){if(x==0||y==0)return0;elsereturns;}

2.8.3分治舉例——大整數(shù)乘法Chapter2else{a=x的左邊n/2位；

b=x的右邊n/2位；

c=y的左邊n/2位；

d=y的右邊n/2位；

m1=MULT(a,c,n/2);m2=MULT(a-b,d-c,n/2);m3=MULT(b,d,n/2);s=s*(m1*2n+(m1+m2+m3)*2n/2+m3)returns;}}2.8.3分治舉例——大整數(shù)乘法Chapter2(1)列出算法的遞歸方程：(2)求解遞歸方程當(dāng)n>1時(shí)，設(shè)n=2k,則k=log2n2.8.3分治舉例——大整數(shù)乘法Chapter2即也可以通過(guò)2.4節(jié)中的主方法求解該遞歸方程：根據(jù)定理1，該遞歸方程中a=3,b=2,T(n)=O(nlog23)2.8.3分治舉例——大整數(shù)乘法Chapter2因?yàn)?滿足主方法中的第(1)種情況，因此結(jié)果表明，我們通過(guò)降低計(jì)算過(guò)程中的乘法運(yùn)算的次數(shù)，降低了該算法的復(fù)雜度，使其更優(yōu)。(3)證明上述求解結(jié)果：當(dāng)時(shí)，假設(shè)時(shí)，成立。則當(dāng)n>m時(shí)，不妨，有：從而得證。2.8.3分治舉例——大整數(shù)乘法Chapter2例2.13：分析：2.8.4分治舉例——折半查找Chapter2問(wèn)題描述：給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。問(wèn)題分析：采用分治的思想，充分利用元素之間的已存在的次序關(guān)系，將排好序的數(shù)組a[0:n-1]劃分成兩個(gè)個(gè)數(shù)相同的左、右兩部份，取a[n/2]與x進(jìn)行比較，如果x=a[n/2],則找到x,算法結(jié)束；如果x>a[n/2]，則在數(shù)組a劃分得到的右半部繼續(xù)查找；如果x<a[n/2],則在數(shù)組a劃分得到的左半部繼續(xù)查找。在數(shù)組a左半部或右半部分繼續(xù)查找x的過(guò)程采用同樣的分治方法。2.8.4分治舉例——折半查找Chapter2按照上述思想，二分搜索算法為：ITERATIVEBINARYSEARCH(A,v,low,high)1whilelow≤high2domid←(low+high)/23ifv=A［mid］4thenreturnmid5elseifv>A［mid］6thenlow←mid+17elsehigh←mid-18returnNIL2.8.4分治舉例——折半查找Chapter2(1)列出該算法的遞歸方程：(2)利用替換法求解該遞歸方程：當(dāng)n>1時(shí)2.8.4分治舉例——折半查找Chapter2

設(shè)n=2k,即k=log2n得到該遞歸方程的解為T(n)=1+log2n=O(log2n)，即該算法的時(shí)間復(fù)雜度為O(log2n)。對(duì)于該算法，我們也可以對(duì)語(yǔ)句執(zhí)行頻度進(jìn)行分析?？煽闯?，該算法中每執(zhí)行一次while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(log2n)趟。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜度為O(log2n)。2.8.4分治舉例——折半查找Chapter2(3)證明log2n是遞歸方程的解當(dāng)n=1時(shí)T(n)=1假設(shè)當(dāng)n=m時(shí)，T(m)=1+log2m=O(log2m)成立當(dāng)n>m時(shí)，不妨n=2m從而證明了log2n是該遞歸方程的解。2.8.5分治舉例——矩陣乘法Chapter2

問(wèn)題描述：設(shè)計(jì)算法，完成矩陣運(yùn)算C=A×B,其中A、B為n×n矩陣。矩陣乘法是線性代數(shù)中最基本的運(yùn)算之一，它在數(shù)值計(jì)算中有廣泛的應(yīng)用。若A和B是2個(gè)n×n矩陣。A和B的乘積矩陣C中的元素為：?jiǎn)栴}分析：根據(jù)該規(guī)則，兩個(gè)n階矩陣相乘時(shí)，算法需要完成3重次數(shù)為n的循環(huán)，算法的時(shí)間復(fù)雜度為，可以利用分治法對(duì)算法進(jìn)行改進(jìn)：2.8.5分治舉例——矩陣乘法Chapter2

設(shè)即：

C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22則C=A×B可劃分為如下形式2.8.5分治舉例——矩陣乘法Chapter2

n=2時(shí)，直接求時(shí)，求子陣乘積，要做8個(gè)n/2子陣相乘，4個(gè)n/2子陣相加，后者的時(shí)間復(fù)雜度為O(n2)。（1）列出以上分治方法的遞歸方程2.8.5分治舉例——矩陣乘法Chapter2

（2）求解決遞