算法分析設計遞歸與分治策略

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

2、模的問題的解，自底向上逐步求出原來問題的解。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ī)模的問題的解合并為一個更大規(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)

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

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

5、為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃

6、較好。分治法的適用條件：9分治法的復雜性分析：一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為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)上升的，從而當minmi+1時，T(mi)T(n)T(mi+1)。

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

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

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

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

11、下1個元素為止。然后不斷合并2個排好序的數(shù)組段。消去遞歸：首先將數(shù)組中的相鄰元素兩兩配對，用合并算法將其排序，構(gòu)成n/2組長度為2的排好序的子數(shù)組段，然后將它們排序成長度為4的排好序的子數(shù)組段，如此繼續(xù)下去，直至整個數(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; /剩下的元素個數(shù)少于2s if(i+sx.length) merge(x,y,I,i+s-1,x.length-1); else /復制到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的元素個數(shù)多 else for(int q=i;q=m;q+) dk+=cq; 2.4 合并排序182.4 合并排序算法改進-自然合并排序如果初始數(shù)組中，存在多個長度大于1且已經(jīng)排好序的子數(shù)組段。則通過1次線性掃描就可以找出所有這些排好