《《算法设计与分析》-第二章 递归与分治》由会员分享，可在线阅读，更多相关《《算法设计与分析》-第二章 递归与分治（39页珍藏版）》请在金锄头文库上搜索。
1、第二章 递归与分治策略,第二章 递归与分治,2.1 分治法的基本思想 2.2 分治法的适用条件 2.3 分治法的基本步骤 2.4 分治法的应用,2.1 分治法（divide-and-conquer）的基本思想,为求解大问题，可以： 分割成k个更小规模的子问题。 对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,将要求解的较大规模的问题分割成k个更小规模的子问题。,2.1 分治法的基本思想,n,T(n/2),T(n/2),T(
2、n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,n,T(n),=,2.1 分治法的基本思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,2.1 分治法的基本思想,2.1 分治法的基本思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治
3、法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。,2.1 分治法的基本思想,2.1 分治法的基本思想,2.2 分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,2.3 分治法的基本步骤,divide-and-conquer(P)if ( | P | = n0) adhoc(P); /解决小规模
4、的问题divide P into smaller subinstances P1,P2,.,Pk；/分解问题for (i=1,i1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。,2.4 分治法的应用,全排列算法,void perm(int list, int k, int m) /产生listkm的所有排列 /其中list0k-1是前缀，后缀是listkm /调用perm(list,0,n-1)则产生list0n-1的全排列 if (k=m)For (i=0;i=m;i+)Printf(“%d ”,listi);Printf(“n”);
5、elseFor(i=k;i0时，将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; / 分割
6、棋盘/ 覆盖左上角子棋盘if (dr = tc + 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 ,复杂度分析T(n)=O(4k) 渐进意义下的最优算法,例6 合并排序,void mergeSort(int a, int left, int right) if (leftright) /至少有
7、2个元素int i=(left+right)/2; /取中点mergeSort(a, left, i);mergeSort(a, i+1, right);merge(a, b, left, i, right); /合并到数组bcopy(a, b, left, right); /复制回数组a,复杂度分析T(n)=O(nlogn) 渐进意义下的最优算法,2.4 分治法的应用,合并排序,算法mergeSort的递归过程可以消去。,非递归的归并排序算法,void MergeSort(int a, int n) s=1; while(sn)MergePass(a,b,s,n);s+=s;MergePas
8、s(b,a,s,n);s+=s; ,void MergePass(int x, inty,int s, int n) i=0; while(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);elsefor(j=i;j=n-1;j+)yj=xj; ,非递归的归并排序算法(续),void Merge (int c,int d,int l,int m,int r)i=l;j=m+1;k=l;while(im) for(q=j;q=r;q+)dk+=cq;else for(q=i;q=m;q+)dk+=
9、cq; ,合并排序,最坏时间复杂度：O(nlogn) 平均时间复杂度：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 (low=pivot)-high;alow=ahigh;while (lowhigh,随机划分：int randomizedPartition (int a,int p, int
10、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)/在apr中找第k小的元素if (p=r) return ap;i=randomizedpartition(p,r),j=i-p+1;if (k=j) return randomizedSelect(a,p,i,k);else return randomizedSelect(a,i+1,r
11、,k-j); 调用randomizedSelect(a,0,n-1, k)即可求得数组a中的第k小元素,2.8 分治法求最大、最小问题,金块问题一老板有一袋金块，每月两名雇员因成绩优异被奖励，排名第一的雇员得最重的金块，排名第二的雇员得到最轻的金块。如有新的金块周期性地加到金袋中，则每月须找出最重、最轻的金块。设有台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。最大、最小问题实例,2.8 分治法求最大、最小问题,bool MinMax(int a,int n,int ,比较次数：n为偶数：1+3(（n-2）/2)=3n/2-2 n为奇数：3(n-1)/2=(3n+1)/2-2=3n/2-2 总之： 3n/2-2次,
