遞歸與分治策略

遞歸與分治策略第一頁，共三十八頁，編輯于2023年，星期五學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計有效算法的分治策略。通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。（1）二分搜索技術(shù)；（2）合并排序和快速排序；主要內(nèi)容:2.0分治法總體思想2.1遞歸：階乘、

Fibonacci和Hanoi2.2分治法的適用條件,

基本步驟,復(fù)雜性分析2.3二分搜索技術(shù)2.4快速排序2.5合并排序總結(jié)第二頁，共三十八頁，編輯于2023年，星期五將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。2.0分治法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。第三頁，共三十八頁，編輯于2023年，星期五2.0算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。第四頁，共三十八頁，編輯于2023年，星期五2.0算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)第五頁，共三十八頁，編輯于2023年，星期五2.0算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)

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

第六頁，共三十八頁，編輯于2023年，星期五2.1遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。下面來看幾個實例。第七頁，共三十八頁，編輯于2023年，星期五2.1遞歸的概念例1階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。第八頁，共三十八頁，編輯于2023年，星期五2.1遞歸的概念例2Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數(shù)可遞歸地計算如下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}第九頁，共三十八頁，編輯于2023年，星期五例2

Fibonacci調(diào)用結(jié)構(gòu)：第十頁，共三十八頁，編輯于2023年，星期五例2

Fib復(fù)雜度分析：

Thecalltreeisafullbinarytreedowntodepthn/2,therightmostpathbeingtheshortest,suchasn,n-2,…,0.(niseven).Therefore,therunningtimeisatleastO(2n/2)第十一頁，共三十八頁，編輯于2023年，星期五ModifytheprocedureofExample2,whichcomputesFibonaccinumbers,touseonlyaconstantnumbersforworkspaceandstillcomputeFninO(n)time.if(n<=1)returnn;prev2=0;prev1=1;for(i=2;i<=n;i++) cur=prev1+prev2; prev2=prev1; prev1=cur;returncur;改進(jìn)Fibonacci

：第十二頁，共三十八頁，編輯于2023年，星期五2.1遞歸的概念例3Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。第十三頁，共三十八頁，編輯于2023年，星期五在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。2.1遞歸的概念例6Hanoi塔問題

voidhanoi(intn,inta,intb,intc){

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}第十四頁，共三十八頁，編輯于2023年，星期五2.1遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計算時間還是占用的存儲空間都比非遞歸算法要多。第十五頁，共三十八頁，編輯于2023年，星期五解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數(shù)。反向遞歸3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。反演變換后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。2.1遞歸小結(jié)第十六頁，共三十八頁，編輯于2023年，星期五2.2分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。第十七頁，共三十八頁，編輯于2023年，星期五divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問題

returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解

}2.2分治法的基本步驟人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。第十八頁，共三十八頁，編輯于2023年，星期五2.2分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。

第十九頁，共三十八頁，編輯于2023年，星期五分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[i]，同理我們只要在a[mid]的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。

分析：很顯然此問題分解出的子問題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個適用條件。2.3二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨(dú)立的。第二十頁，共三十八頁，編輯于2023年，星期五2.3二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。第二十一頁，共三十八頁，編輯于2023年，星期五2.4QuicksortQuicksortStrategy:

通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄遞歸地繼續(xù)分別進(jìn)行排序，以達(dá)到整個序列有序。

C.A.R.Hoare(TonyHoare)教授，1980年獲得美國計算機(jī)學(xué)會(ACM)設(shè)立的計算機(jī)界最高獎——圖靈獎第二十二頁，共三十八頁，編輯于2023年，星期五2.4快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序

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

}}第二十三頁，共三十八頁，編輯于2023年，星期五template<classType>intPartition(Typea[],intp,intr){inti=p+1,j=r;Typex=a[p];//將<x的元素交換到左邊區(qū)域

//將>x的元素交換到右邊區(qū)域

while(true){while(a[i]<x){i++;}while(a[j]>x){j--;}if(i>=j)break;Swap(a[i],a[j])i++;j--;}a[p]=a[j];a[j]=x;returnj;}2.4快速排序:Partition方法1正確嗎?第二十四頁，共三十八頁，編輯于2023年，星期五2.4一趟快速排序的算法是：Partition方法21）設(shè)置兩個變量I、J，排序開始的時候：I=0，J=N-1；2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個小于key的值A(chǔ)[J]，并與A[I]交換；4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個大于key的A[I]，與A[J]交換；5）重復(fù)第3、4、5步，直到I=J；(3,4步是在程序中沒找到時候j=j-1，i=i+1。找到并交換的時候i，j指針位置不變。另外當(dāng)i=j這過程一定正好是i+或j+完成的最后另循環(huán)結(jié)束)第二十五頁，共三十八頁，編輯于2023年，星期五2.4Quicksort:example初始關(guān)鍵字：{49，38，65，97，76，13，27，49}pivotkey49jji1次交換后：{27，38，65，97，76，13，，49}iji2次交換后：{27，38，，97，76，13，65，49}ijj3次交換后：{27，38，13，97，76，，65，49}iji4次交換后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}第二十六頁，共三十八頁，編輯于2023年，星期五2.4AnalysisofQuicksort:worstcase情況：劃分后產(chǎn)生的兩區(qū)域分別包含n-1和1個元素第二十七頁，共三十八頁，編輯于2023年，星期五2.4AnalysisofQuicksort:averagebehavior方法1第二十八頁，共三十八頁，編輯于2023年，星期五2.4AnalysisofQuicksort:averagebehavior：方法1第二十九頁，共三十八頁，編輯于2023年，星期五2.4AnalysisofQuicksort:averagebehavior方法2可得其解：T(n)=O(nlogn)第三十頁，共三十八頁，編輯于2023年，星期五2.5合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){

if(left<right){//至少有2個元素

inti=(left+right)/2;//取中點(diǎn)

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到數(shù)組b

copy(a,b,left,right);//復(fù)制回數(shù)組a}}第三十一頁，共三十八頁，編輯于2023年，星期五2.5合并排序算法mergeSort的遞歸過程可以消去。重點(diǎn)講