1、算法總體思想將要求解的較大規模的問題分割成k個更小規模的子問題。1算法總體思想對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規模足夠小，很容易求出其解為止。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)將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解。2算法總體思想將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上

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)3算法總體思想將求出的小規模的問題的解合并為一個更大規模的問題的解，自底向上逐步求出原來問題的解。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、一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。凡治眾如治寡，分數是也。-孫子兵法42.1 遞歸的概念直接或間接地調用自身的算法稱為遞歸算法。用函數自身給出定義的函數稱為遞歸函數。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。下面來看幾個實例。52.1 遞歸的概念例1 階乘函數階乘函數可遞歸地定義為：邊界條件遞歸方程

4、邊界條件與遞歸方程是遞歸函數的二個要素，遞歸函數只有具備了這兩個要素，才能在有限次計算后得出結果。62.1 遞歸的概念例2 Fibonacci數列無窮數列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci數列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數可遞歸地計算如下：public static int fibonacci(int n) if (n 0) hanoi(n-1, a, c, b); move(a,c); hanoi(n-1, b, c, a); 思考題：如果塔的個數變為a,b,c,d四個，現要將n個圓盤從a全部移動到d，移動規則不變，求移

5、動步數最小的方案。8遞歸小結優點：結構清晰，可讀性強，而且容易用數學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。9遞歸小結解決方法：在遞歸算法中消除遞歸調用，使其轉化為非遞歸算法。1.采用一個用戶定義的棧來模擬系統的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優化效果不明顯。2.用遞推來實現遞歸函數。3.通過Cooper變換、反演變換能將一些遞歸轉化為尾遞歸，從而迭代求出結果。 后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。10分治法

6、的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 因為問題的計算復雜性一般是隨著問題規模的增加而增加，因此大部分問題滿足這個特征。這條特征是應用分治法的前提，它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態規劃。這條特征涉及到分治法的效率，如

7、果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然也可用分治法，但一般用動態規劃較好。11分治法的基本步驟divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 人們從大量實踐中發現，在用分治法設計算法時，最好使子

8、問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。12分治法的復雜性分析一個分治法將規模為n的問題分成k個規模為nm的子問題去解。設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果

9、認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調上升的，從而當minmi+1時，T(mi)T(n)T(mi+1)。 13二分搜索技術分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規模縮小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的

10、子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出一特定元素x。分析：該問題的規模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。 14二分搜索技術給定已按升序排好序的n個元素a0:n-1，現要在這n個元素中找出一特定元素x。據此容易設計出二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = a

11、n-1 中搜索 x / 找到x時返回其在數組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法復雜度分析：每執行一次算法的while循環， 待搜索數組的大小減少一半。因此，在最壞情況下，while循環被執行了O(logn) 次。循環體內運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為O(logn) 。思考題：給定a，用二分法設計出求an的算法。15合并排序基本思想：將待

12、排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 public static void mergeSort(Comparable a, int left, int right) if (left= x的元素交換到左邊區域 / 將= x的元素交換到右邊區域 while (true) while (a+pareTo(x) 0); if (i = j) break; MyMath.swap(a, i, j); ap = aj; aj = x; return j; 初始序列6, 7, 5, 2, 5, 8j-;5, 7, 5, 2, 6

13、, 8i+;5, 6, 5, 2, 7, 8j-;5, 2, 5, 6, 7, 8i+;完成快速排序具有不穩定性。6, 7, 5, 2, 5, 85, 2, 5 6 7, 819private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序 快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設計出采用隨機選擇策略的快速排序算法。在快速排序算法的每一步中，當數組還沒有被劃分時，可以在a

14、p:r中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。最壞時間復雜度：O(n2)平均時間復雜度：O(nlogn)輔助空間：O(n)或O(logn)穩定性：不穩定20大整數的乘法 請設計一個有效的算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2) 效率太低分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 為了降低時間復雜度，必須減少乘法的次數。XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bdXY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd復雜度分析T(n)

15、=O(nlog3) =O(n1.59)較大的改進細節問題：兩個XY的復雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結果，使問題的規模變大，故不選擇第2種方案。21大整數的乘法 請設計一個有效的算法，可以進行兩個n位大整數的乘法運算小學的方法：O(n2) 效率太低分治法: O(n1.59) 較大的改進更快的方法?如果將大整數分成更多段，用更復雜的方式把它們組合起來，將有可能得到更優的算法。最終的，這個思想導致了快速傅利葉變換(Fast Fourier Transform)的產生。該方法也可以看作是一個復雜的分治算法，對于大整數乘法，它能在O(nlogn)時間內解決。是否能找

16、到線性時間的算法？目前為止還沒有結果。22Strassen矩陣乘法A和B的乘積矩陣C中的元素Ci,j定義為: 若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個元素所需的計算時間為O(n3)傳統方法：O(n3)23Strassen矩陣乘法使用與上例類似的技術，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：傳統方法：O(n3)分治法:由此可得：復雜度分析T(n)=O(n3) 沒有改進24Strassen矩陣乘法傳統方法：O(n3)分治法:為了降低時間復雜度，必須減少乘法的次數。復雜度分析T(n

17、)=O(nlog7) =O(n2.81)較大的改進25Strassen矩陣乘法傳統方法：O(n3)分治法: O(n2.81)更快的方法?Hopcroft和Kerr已經證明(1971)，計算2個矩陣的乘積，7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算22矩陣的7次乘法這樣的方法了?；蛟S應當研究或矩陣的更好算法。在Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是 O(n2.376)是否能找到O(n2)的算法？目前為止還沒有結果。26棋盤覆蓋在一個2k2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且

18、稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。27棋盤覆蓋當k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。 28棋盤覆蓋 public void chessBoard(int tr, int tc, int dr

19、, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號 s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr tr + s & dc tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤 if (dr = tc

20、 + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號L型骨牌覆蓋左上角 boardtr + stc +

21、 s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 復雜度分析T(n)=O(4k) 漸進意義下的最優算法29Linear-Time SelectionGiven an array A of n numbers A1.n and a number k (1kn), find the kth smallest number in A.the median is the n/ 2th smallest element Example: If A=(7, 4, 8, 2, 4); then |A| = 5 and the 3rd smalle

22、st element (and median) is 4.solutions for our problem:General approach: Sort the array ( heap, merge) O(nlogn) return the kth element. O(1) Total Execution time Q(n log n)There is a linear-time selection algorithm30Strategy1: Partition-based (quick sort) selectionChoose one element p from array A (

23、pivot element)Split input into three sets: LESS: elements from A that are smaller than p EQUAL: elements from A that are equal to p MORE: elements from A that are greater than pWe have three cases: i |L| the element we are looking for is also the ithsmallest number in L |L| i |L| + |E| the element w

24、e are looking for is p. |L| + |E| ithe element we are looking for is the(i - |L| - |E|)th smallest element in M.This takes O(n) in the best and average case, Unfortunatelly the running time can grow to O(n2) in the worst case.31Linear Time selection algorithmProcedure select (A, lowhigh, k)If n is s

25、mall, for example n5, then partition the numbers into groups of 5. (time n/5)Sort the elements in each group. Select the middle elements (medians). (time- 7n/5)Select the median of the medians mmPartition the (n-1) elements into 3 lists (L,R,M) according to mm. L Ai mmM Ai = mmNote that the rank of

26、m is r=|L|+1 (|L| is the size of L). (time- n)And so case: k=r return mkr return k-r th smallest of set R. select (A, r+1.|R|, k-r th )32Examplethe median is the kth element such that k = 25/ 2 =13. divide into 5 groups (8, 33, 17, 51, 57)(49, 35, 11, 25, 37) (14, 3, 2, 13, 52) (12, 6, 29, 32, 54) (

27、5, 16, 22, 23, 7).Sort each group(8, 17, 33, 51, 57)(11, 25, 35, 37, 49)(2, 3, 13, 14, 52)(6, 12, 29, 32, 54)(5, 7, 16, 22, 23). Extract the median of each group M = 33, 35, 13, 29, 16. median of medians mm = 29:partition A into three sequences:L = 8, 17, 11, 25, 14, 3, 2, 13, 12, 6, 5, 16, 22, 23,

28、7M = 29, R = 33, 51, 57, 49, 35, 37, 52, 32, 54 33Example cont.L = 8, 17, 11, 25, 14, 3, 2, 13, 12, 6, 5, 16, 22, 23, 7We repeat the same procedure above: select (L, 1,|L|, k)So we set A = L. We divide the elements into 3 groups of 5 elements each: (8,17,11,25,14), (3,2,13,12,6), (5,16,22,23,7).Sort

29、 each of the group, and find the new set of medians: M = 14, 6, 16.the new median of medians mm is 14.Next, partition A into three sequences:L = 8, 11, 3, 2, 13, 12, 6, 5, 7,M = 14 andR = 17, 25, 16, 22, 23 .Since 13 10 = A1+A2, we set A = A3 and find the 3rd element in A (3 = 13 - 10). The algorith

30、m will return A3 = 22. Thus, the median of the numbers in the given sequence is 22.34線性時間選擇給定線性序集中n個元素和一個整數k，1kn，要求找出這n個元素中第k小的元素private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=randomizedpartition(p,r), j=i-p+1; if (k=j) return randomizedSelect(p,i,k); else re

31、turn randomizedSelect(i+1,r,k-j); 在最壞情況下，算法randomizedSelect需要O(n2)計算時間但可以證明，算法randomizedSelect可以在O(n)平均時間內找出n個輸入元素中的第k小元素。35線性時間選擇如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的2個子數組的長度都至少為原數組長度的倍(01是某個正常數)，那么就可以在最壞情況下用O(n)時間完成選擇任務。例如，若=9/10，算法遞歸調用所產生的子數組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可

32、得T(n)=O(n)。36將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數，共n/5個。遞歸調用select來找出這n/5個元素的中位數。如果n/5是偶數，就找它的2個中位數中較大的一個。以這個元素作為劃分基準。線性時間選擇設所有元素互不相同。在這種情況下，找出的基準x至少比3(n-5)/10個元素大，因為在每一組中有2個元素小于本組的中位數，而n/5個中位數中又有(n-5)/10個小于基準x。同理，基準x也至少比3(n-5)/10個元素小。而當n75時，3(n-5)/10n/4所以按此基準劃分所得的2個子數

33、組的長度都至少縮短1/4。37private static Comparable select (int p, int r, int k) if (r-p5) /用某個簡單排序算法對數組ap:r排序; bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素 /與ap+i交換位置; /找中位數的中位數，r-p-4即上面所說的n-5 for ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4; for (int j=0;j3;j+) bubble(s,t-j); MyMath.swap(a, p

34、+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); 復雜度分析T(n)=O(n)上述算法將每一組的大小定為5，并選取75作為是否作遞歸調用的分界點。這2點保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關鍵之處。當然，除了5和75之外，還有其他選擇。38最接近點對問題給定平面上n個

35、點的集合S，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。 為了使問題易于理解和分析，先來考慮一維的情形。此時，S中的n個點退化為x軸上的n個實數 x1,x2,xn。最接近點對即為這n個實數中相差最小的2個實數。假設我們用x軸上某個點m將S劃分為2個子集S1和S2 ，基于平衡子問題的思想，用S中各點坐標的中位數來作分割點。遞歸地在S1和S2上找出其最接近點對p1,p2和q1,q2，并設d=min|p1-p2|,|q1-q2|，S中的最接近點對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2。能否在線性時間內找到p3,q3？39最接近點對問題如

36、果S的最接近點對是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過d，即p3(m-d,m，q3(m,m+d。由于在S1中，每個長度為d的半閉區間至多包含一個點（否則必有兩點距離小于d），并且m是S1和S2的分割點，因此(m-d,m中至多包含S中的一個點。由圖可以看出，如果(m-d,m中有S中的點，則此點就是S1中最大點。因此，我們用線性時間就能找到區間(m-d,m和(m,m+d中所有點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。能否在線性時間內找到p3,q3？40最接近點對問題下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S

37、中各點x坐標的中位數。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設d=mind1,d2，S中的最接近點對或者是d，或者是某個p,q，其中pP1且qP2。能否在線性時間內找到p,q？41最接近點對問題考慮P1中任意一點p，它若與P2中的點q構成最接近點對的候選者，則必有distance(p，q)d。滿足這個條件的P2中的點一定落在一個d2d的矩形R中由d的意義可知，P2中任何2個S中的點的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點。因此，在分治法的合并步驟中最多只需要檢查6n/2=3n個候選者能否在線性時間內找到p3,q3？證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導