1、算法设计与分析算法设计与分析- -第二章第二章 递归递归与分治与分治1710317103第二章第二章 递归与分治递归与分治l2.1 分治法的基本思想l2.2 分治法的适用条件l2.3 分治法的基本步骤l2.4 分治法的应用2.1 分治法（分治法（divide-and-conquer）的基本）的基本思想思想l为求解大问题，可以：分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。l将要求解的较大规模的问题
2、分割成k个更小规模的子问题。2.1 分治法的基本思想分治法的基本思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= l对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。l对这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
3、/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想l将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。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 分治法的基本思想分治法的基本思想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
4、/2T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想l将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是，将一个难以直接解决的大分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。个击破，分而治之。2.1 分治法的基本思想分治法的基本思想2.1 分治法的基本思想分治法的基本思想2.2 分治法的适用条件分治法的适用条件l该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；l该
5、问题可以分解为若干个规模较小的相同问题，即该该问题可以分解为若干个规模较小的相同问题，即该问题具有问题具有最优子结构性质最优子结构性质l利用该问题分解出的子问题的解可以合并为该问题的利用该问题分解出的子问题的解可以合并为该问题的解；解；l该问题所分解出的各个子问题是相互独立的，即子问该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。 2.3 分治法的基本步骤分治法的基本步骤divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinst
6、ances P1,P2,.,Pk；/分解问题 for (i=1,i1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。 2.4 分治法的应用分治法的应用全排列算法全排列算法lvoid perm(int list, int k, int m) l/产生listk.m的所有排列l/其中list0.k-1是前缀，后缀是listk.ml/调用perm(list,0,n-1)则产生list0.n-1的全排列lif (k=m)l For (i=0;i=m;i+)l Printf(“%d ”,listi);l Printf(“n”);llelsel For
7、(i=k;i=m;i+)l Swap(listk,listi);l Perm(list,k+1,m);l Swap(listk,listi);l ll例例3 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个个元素中找出一特定元素元素中找出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的
8、各个子问题是相互独立的。 2.4 分治法的应用分治法的应用二分搜索算法二分搜索算法：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 l例例3 2.4 分治法的应用分治法的应用A和B的乘积矩阵C中的元素Ci,j定义为: nkjkBkiAjiC1u传统方法：O(n3)l例例4 2.4 分治法的应用分治法的应用使用与上例类似的技术，将矩阵A，B和C中每一矩阵都
9、分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3) 没有改进没有改进22)()2/(8) 1 ()(2nnnOnTOnTu改进:为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBA
10、M)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进22)()2/(7) 1 ()(2nnnOnTOnT例例5 在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.4 分治法的应用分治法的应用当k0时，将
11、2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。 void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr
12、 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, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1t
13、c + 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, tr+s, tc+s, s); 复杂度分析复杂度分析T(n)=O(4k) 渐进意义下的最优算法00) 1 () 1(4)
14、1 ()(kkOkTOkTl例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); /合并到数组b copy(a, b, left, right); /复制回数组a 复杂度分析复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法11)()2/(2) 1 ()(nnnOnTOnT2.4 分治法的应用分
15、治法的应用算法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非递归的归并排序算法非递归的归并排序算法void MergeSort(int a, int n)s=1;while(sn) MergePass(a,b,s,n); s+=s; MergePass(b,a,s,n); s+=s;lvoid MergePass(int x, inty,int s, int n)li=0;lwhile(i=n-2*s)l Merge
16、(x,y,i,i+s-1,i+2*s-1);l i=i+2*s;ll if(i+sn)l Merge(x,y,i,i+s-1,n-1);l elsel for(j=i;j=n-1;j+)l yj=xj;l非递归的归并排序算法非递归的归并排序算法(续续)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;&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度
17、：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定2.4 分治法的应用分治法的应用2.4 分治法的应用分治法的应用给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素例例7 元素元素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; return
18、 low; 随机划分：int randomizedPartition (int a,int p, int r) i = random(p,r); swap(ai, ap); return partition (a,p, r); 给定线性序集中n个元素和一个整数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=i-p+1; if (k=j) return randomizedSelect(a
19、,p,i,k); else return randomizedSelect(a,i+1,r,k-j); 调用randomizedSelect(a,0,n-1, k)即可求得数组a中的第k小元素2.8 l金块问题一老板有一袋金块，每月两名雇员因成绩优异被奖励，排名第一的雇员得最重的金块，排名第二的雇员得到最轻的金块。如有新的金块周期性地加到金袋中，则每月须找出最重、最轻的金块。设有台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。 最大、最小问题实例2.8 ABCDEFGabcdefghbool MinMax(int a,int n,int &min,int &max) If (na1) min=1;max=0;s=2 else min=0;max=1;s=2 for(i=s; iai+1) if(aiamax) max=i; if(ai+1amax) max=i+1; if(aiamin) min=i; 比较次数：n为偶数：1+3(（n-2）/2)=3n/2-2n为奇数：3(n-1)/2=(3n+1)/2-2=3n/2-2总之： 3n/2-2次习题：习题：l写出二分搜索的递归算法l写出求n个元素中最大、最小值的递归代码。
