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

1、第2章 遞歸與分治策略2.1遞歸的概念2.2分治的基本思想2.3二分搜索技術(shù)2.4合并排序本章主要知識(shí)點(diǎn)：1算法總體思想分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的問(wèn)題，以便各個(gè)擊破，分而治之。如果由分治法產(chǎn)生的子問(wèn)題是原問(wèn)題的較小規(guī)模，則可以用遞歸技術(shù)解決。2將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。3算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)

2、模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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)4算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。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)

3、52.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。下面來(lái)看幾個(gè)實(shí)例。62.1 遞歸的概念例1 階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件（非遞歸定義）與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。7

4、2.1 遞歸的概念例4 排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 82.2 分治法的基本思想分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解

5、為若干個(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)題。 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃

6、較好。分治法的適用條件：9分治法的復(fù)雜性分析：一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)題的解合并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有：通過(guò)迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。

7、102.3 二分搜索技術(shù)分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x

8、。分析：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 112.3 二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x時(shí)返回其在數(shù)組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left

9、amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。思考題：給定a，用二分法設(shè)計(jì)出求an的算法。122.4 合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 public static voi

10、d mergeSort(Comparable a, int left, int right) if (leftright) /至少有2個(gè)元素 int i=(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ù)制回?cái)?shù)組a 復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法13算法分析：2.4 合并排序算法mergeSort的遞歸過(guò)程只是將待排序集合一分為二，直至待排序的集合只剩

11、下1個(gè)元素為止。然后不斷合并2個(gè)排好序的數(shù)組段。消去遞歸：首先將數(shù)組中的相鄰元素兩兩配對(duì)，用合并算法將其排序，構(gòu)成n/2組長(zhǎng)度為2的排好序的子數(shù)組段，然后將它們排序成長(zhǎng)度為4的排好序的子數(shù)組段，如此繼續(xù)下去，直至整個(gè)數(shù)組排好序。142.4 合并排序例如：初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97152.4 合并排序按此思想消去遞歸后的合并排序算法可描述如下： public static void mergeSort(Comparable a) Comp

12、arable b=new Comparablea.length; int s=1; while(sa.length) mergePass(a,b,s); /合并到數(shù)組b s=s+1; mergePass(b,a,s); /合并到數(shù)組a s=s+1; 162.4 合并排序其中，算法mergePass用于合并排好序的相鄰數(shù)組： public static void mergePass(Comparable x，Comparable y,int s) /合并大小為s的相鄰子數(shù)組 int i; while(i=x.length-2*s) /合并大小為s的相鄰2段子數(shù)組 merge(x,y,I,i+s-

13、1,i+2*s-1); i=i+2*s; /剩下的元素個(gè)數(shù)少于2s if(i+sx.length) merge(x,y,I,i+s-1,x.length-1); else /復(fù)制到y(tǒng) for(int j=i;jx.length;j+) yj=xj; 17 public static void merge (Comparable c，Comparable d,int l,int m,int r) /合并c1:m和cm+1:r到d1:r int i=l,j=m+1,k=l; while(i=m)&(j=r) if(pareTo(cj)=0)/如果cim) for(int q=j;q=r;q+) dk+=cq; /cm+1:r的元素個(gè)數(shù)多 else for(int q=i;q=m;q+) dk+=cq; 2.4 合并排序182.4 合并排序算法改進(jìn)-自然合并排序如果初始數(shù)組中，存在多個(gè)長(zhǎng)度大于1且已經(jīng)排好序的子數(shù)組段。則通過(guò)1次線性掃描就可以找出所有這些排好