《算法設(shè)計與分析》-第二章-遞歸與分治17103課件(PPT 39頁)

1、算法設(shè)計與分析-第二章 遞歸與分治17103第1頁，共39頁。第二章 遞歸與分治2.1 分治法的基本思想2.2 分治法的適用條件2.3 分治法的基本步驟2.4 分治法的應(yīng)用第2頁，共39頁。2.1 分治法（divide-and-conquer）的基本思想為求解大問題，可以：分割成k個更小規(guī)模的子問題。對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。第3頁，共39頁。將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。2.1 分

2、治法的基本思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。第4頁，共39頁。對這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)2.1 分

3、治法的基本思想第5頁，共39頁。將求出的小規(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)2.1 分治法的基本思想第6頁，共39頁。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

4、)T(n/4)2.1 分治法的基本思想將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。第7頁，共39頁。分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。2.1 分治法的基本思想第8頁，共39頁。2.1 分治法的基本思想第9頁，共39頁。2.2 分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子

5、問題之間不包含公共的子問題。 第10頁，共39頁。2.3 分治法的基本步驟divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 2.4 分治法的應(yīng)用第17頁，共39頁。全排列算法void perm(int list, int k, int m) /產(chǎn)生listk.m的所有排列/其中l(wèi)ist0.k-1是前綴

6、，后綴是listk.m/調(diào)用perm(list,0,n-1)則產(chǎn)生list0.n-1的全排列if (k=m) For (i=0;i=m;i+) Printf(“%d ”,listi); Printf(“n”);else For(i=k;i=m;i+) Swap(listk,listi); Perm(list,k+1,m); Swap(listk,listi); 第18頁，共39頁。例3 二分搜索技術(shù)給定已按升序排好序的n個元素a0:n-1，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并

7、為原問題的解；分解出的各個子問題是相互獨立的。 2.4 分治法的應(yīng)用第19頁，共39頁。二分搜索算法：int binarySearch(int a, int x, int n) left = 0; right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 思考題：寫出二分搜索的遞歸算法。例3 二分搜索技術(shù)2.4 分治法的應(yīng)用第20頁，共39頁。A和B的乘積矩陣C中的元素Ci,j定義為: 傳統(tǒng)方法：O(n3)例4 Strassen矩陣乘法2.4 分治法的應(yīng)用第

8、21頁，共39頁。Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：分治法:由此可得：復(fù)雜度分析T(n)=O(n3) 沒有改進(jìn)第22頁，共39頁。Strassen矩陣乘法改進(jìn):為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog7) =O(n2.81)較大的改進(jìn)第23頁，共39頁。例5 棋盤覆蓋在一個2k2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格

9、，且任何2個L型骨牌不得重疊覆蓋。2.4 分治法的應(yīng)用第24頁，共39頁。棋盤覆蓋當(dāng)k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。 第25頁，共39頁。棋盤覆蓋void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return

10、; 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 + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, d

11、r, 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 + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s,

12、tr+s, tc+s, s); 復(fù)雜度分析T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法第26頁，共39頁。例6 合并排序void mergeSort(int 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); /復(fù)制回數(shù)組a 復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算

13、法2.4 分治法的應(yīng)用第27頁，共39頁。合并排序算法mergeSort的遞歸過程可以消去。初始序列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 97第28頁，共39頁。非遞歸的歸并排序算法void MergeSort(int a, int n)s=1;while(sn) MergePass(a,b,s,n); s+=s; MergePass(b,a,s,n); s+=s;void MergePass(int x, inty,int s, int n)i=0;whil

14、e(i=n-2*s) Merge(x,y,i,i+s-1,i+2*s-1); i=i+2*s; if(i+sn) Merge(x,y,i,i+s-1,n-1); else for(j=i;j=n-1;j+) yj=xj;第29頁，共39頁。非遞歸的歸并排序算法(續(xù))void Merge (int c,int d,int l,int m,int r) i=l;j=m+1;k=l; while(i=m&j=r) if(cim) for(q=j;q=r;q+) dk+=cq; else for(q=i;q=m;q+) dk+=cq;第30頁，共39頁。合并排序最壞時間復(fù)雜度：O(nlogn)平均時間

15、復(fù)雜度：O(nlogn)輔助空間：O(n)穩(wěn)定性：穩(wěn)定2.4 分治法的應(yīng)用第31頁，共39頁。2.4 分治法的應(yīng)用給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素例7 元素選擇問題第32頁，共39頁。快速排序中的劃分int partition (int a, int p, int r) pivot=ap; low = p; high = r; while (lowhigh) while (low=pivot) -high; alow=ahigh; while (lowhigh&alow =pivot); +low; ahigh=alow; alow = pivot;

16、 return low; 第33頁，共39頁。隨機(jī)劃分：int randomizedPartition (int a,int p, int r) i = random(p,r); swap(ai, ap); return partition (a,p, r); 快速排序中的劃分(續(xù))第34頁，共39頁。元素選擇給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素randomizedSelect(int a,int p,int r,int k) /在ap.r中找第k小的元素 if (p=r) return ap; i=randomizedpartition(p,r), j

17、=i-p+1; if (k=j) return randomizedSelect(a,p,i,k); else return randomizedSelect(a,i+1,r,k-j); 調(diào)用randomizedSelect(a,0,n-1, k)即可求得數(shù)組a中的第k小元素第35頁，共39頁。2.8 分治法求最大、最小問題金塊問題一老板有一袋金塊，每月兩名雇員因成績優(yōu)異被獎勵，排名第一的雇員得最重的金塊，排名第二的雇員得到最輕的金塊。如有新的金塊周期性地加到金袋中，則每月須找出最重、最輕的金塊。設(shè)有臺比較重量的儀器，希望用最少的比較次數(shù)找出最重和最輕的金塊。 最大、最小問題實例第36頁，共39頁。2.8 分治法求最大、最小問題ABCDEFGabcdefgh第37頁，共39頁。bool MinMax(int a