《《算法设计与分析》-第二章 递归与分治课件》由会员分享，可在线阅读，更多相关《《算法设计与分析》-第二章 递归与分治课件（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,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,大量实践证明：在用分治法设计算法时，将一个问题分成大小相等的k个子问题的处理方法是行之有效的,复杂性分析： 设一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合
5、并为原问题的解需用f(n)个单位时间。则有：,通过迭代法求得方程的解：,2.3 分治法的基本步骤,2.4 分治法的应用,分治算法通常采用递归操作实现。但并非所有的递归函数都是分治算法。,2.4 分治法的应用,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,2.4 分治法的应用,例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,2.4 分治法的应用,例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,例3 排列
6、问题 设计一个递归算法生成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)构成。,2.4 分治法的应用,全排列算法,void perm(int list, int k, int m) /产生listk.m的所有排列 /其中lis
7、t0.k-1是前缀，后缀是listk.m /调用perm(list,0,n-1)则产生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); ,例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 ,思考题：写出二分搜索的递归算法。,例3 二分搜索技术,2.4 分治法的应用,A和B的乘积矩阵C中的元素Ci,j定义为:,传统方法：O(n3),例4 Strassen矩阵乘法,2.4 分治法的应用,Str
9、assen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,分治法:,由此可得：,复杂度分析 T(n)=O(n3) 没有改进,Strassen矩阵乘法,改进:,为了降低时间复杂度，必须减少乘法的次数。,复杂度分析 T(n)=O(nlog7) =O(n2.81)较大的改进,例5 棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,2.
10、4 分治法的应用,棋盘覆盖,当k0时，将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
11、; / 分割棋盘 / 覆盖左上角子棋盘 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
12、 (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) 渐进意义下的最优算法,2.4 分治法的应用,合并排序,算法mergeSort的递归过程可以消去。,非递归的归并排序算法,void MergeSort(int a, int n) s=1; while(sn) MergePa
13、ss(a,b,s,n); s+=s; MergePass(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); else for(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=
14、r;q+) dk+=cq; else for(q=i;q=m;q+) dk+=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 ,随机
15、划分： 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,p,i,k); else return randomizedSelect(a,i+1,r,k-j); 调用randomizedSelect(a,0,n-1, k)即可求得数组a中的第k小元素,2.8 分治法求最大、最小问题,金块问题一老板有一袋金块，每月两名雇员因成绩优异被奖励，排名第一的雇员得最重的金块，排名第二的雇员得到最轻的金块。如有新的金块周期性地加到金袋中，则每月须找出最重、最轻的金块。设有台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。 最大、最小问题实例,2.8 分治法求最大、最小问题,bool MinMa
