算法分析設(shè)計遞歸與分治策略

算法分析設(shè)計遞歸與分治策略第一頁，共二十頁，編輯于2023年，星期三算法總體思想分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的問題，以便各個擊破，分而治之。

如果由分治法產(chǎn)生的子問題是原問題的較小規(guī)模，則可以用遞歸技術(shù)解決。第二頁，共二十頁，編輯于2023年，星期三將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。第三頁，共二十頁，編輯于2023年，星期三算法總體思想將求出的小規(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年，星期三算法總體思想將求出的小規(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.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遞歸的概念例4排列問題設(shè)計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：

當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；當n>1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。

第八頁，共二十頁，編輯于2023年，星期三2.2分治法的基本思想分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。分治法的適用條件：第九頁，共二十頁，編輯于2023年，星期三分治法的復(fù)雜性分析：一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。第十頁，共二十頁，編輯于2023年，星期三2.3二分搜索技術(shù)分析：如果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小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。

分析：很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。第十一頁，共二十頁，編輯于2023年，星期三2.3二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：publicstaticintbinarySearch(int[]a,intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x時返回其在數(shù)組中的位置，否則返回-1intleft=0;intright=n-1;

while(left<=right){intmiddle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])left=middle+1;

elseright=middle-1;}

return-1;//未找到x}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。思考題：給定a，用二分法設(shè)計出求an的算法。第十二頁，共二十頁，編輯于2023年，星期三2.4合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。publicstaticvoidmergeSort(Comparablea[],intleft,intright){

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

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

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}}復(fù)雜度分析T(n)=O(nlogn)漸進意義下的最優(yōu)算法第十三頁，共二十頁，編輯于2023年，星期三算法分析：2.4合并排序算法mergeSort的遞歸過程只是將待排序集合一分為二，直至待排序的集合只剩下1個元素為止。然后不斷合并2個排好序的數(shù)組段。消去遞歸：首先將數(shù)組中的相鄰元素兩兩配對，用合并算法將其排序，構(gòu)成n/2組長度為2的排好序的子數(shù)組段，然后將它們排序成長度為4的排好序的子數(shù)組段，如此繼續(xù)下去，直至整個數(shù)組排好序。第十四頁，共二十頁，編輯于2023年，星期三2.4合并排序例如：初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]第十五頁，共二十頁，編輯于2023年，星期三2.4合并排序按此思想消去遞歸后的合并排序算法可描述如下：publicstaticvoidmergeSort(Comparablea[]){Comparableb[]=newComparable[a.length];ints=1;while(s<a.length){mergePass(a,b,s);//合并到數(shù)組bs=s+1;mergePass(b,a,s);//合并到數(shù)組as=s+1;}}第十六頁，共二十頁，編輯于2023年，星期三2.4合并排序其中，算法mergePass用于合并排好序的相鄰數(shù)組：publicstaticvoidmergePass(Comparablex[]，Comparabley[],ints)//合并大小為s的相鄰子數(shù)組{inti;while(i<=x.length-2*s){//合并大小為s的相鄰2段子數(shù)組merge(x,y,I,i+s-1,i+2*s-1);i=i+2*s;}//剩下的元素個數(shù)少于2sif(i+s<x.length)merge(x,y,I,i+s-1,x.length-1);else//復(fù)制到y(tǒng)

for(intj=i;j<x.length;j++)y[j]=x[j];}第十七頁，共二十頁，編輯于2023年，星期三publicstaticvoidmerge(Comparablec[]，Comparabled[],intl,intm,intr)//合并c[1:m]和c[m+1:r]到d[1:r]{inti=l,j=m+1,k=l;while((i<=m)&&(j<=r)){if(c[i].compareTo(c[j])<=0)//如果c[i]<=c[j]d[k++]=c[i++];//d[k]=c[i];k=k+1;i=i+1elsed[k++]=c[j++];}/