《算法设计与分析》-第二章-递归与分治17103-405.ppt

算法设计与分析算法设计与分析-第二章第二章 递归与递归与分治分治1710317103第二章第二章 递归与分治递归与分治l2.1 分治法的基本思想l2.2 分治法的适用条件l2.3 分治法的基本步骤l2.4 分治法的应用2.1 分治法（分治法（divide-and-conquer）的基本）的基本思想思想l为求解大问题，可以：分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。l将要求解的较大规模的问题分割成k个更小规模的子问题。2.1 分治法的基本思想分治法的基本思想nT(n/2)T(n/2)T(n/2)T(n/2)T(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)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/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)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(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)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)2.1 分治法的基本思想分治法的基本思想l将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是，将一个难以直接解决的大分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。个击破，分而治之。2.1 分治法的基本思想分治法的基本思想2.1 分治法的基本思想分治法的基本思想2.2 分治法的适用条件分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：l该问题的的规模模缩小到一定的程度就可以容易地解决；小到一定的程度就可以容易地解决；l该问题可以分解可以分解为若干个若干个规模模较小的相同小的相同问题，即，即该问题具有具有最优子结构性质最优子结构性质l利用利用该问题分解出的子分解出的子问题的解可以合并的解可以合并为该问题的的解；解；l该问题所分解出的各个子所分解出的各个子问题是相互独立的，即子是相互独立的，即子问题之之间不包含公共的子不包含公共的子问题。2.3 分治法的基本步骤分治法的基本步骤divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 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 分治法的应用分治法的应用全排列算法全排列算法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(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。分析：分析：该问题的的规模模缩小到一定的程度就可以容易地解决；小到一定的程度就可以容易地解决；该问题可以分解可以分解为若干个若干个规模模较小的相同小的相同问题;分解出的子分解出的子问题的解可以合并的解可以合并为原原问题的解；的解；分解出的各个子分解出的各个子问题是相互独立的。是相互独立的。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定义为:u传统方法：O(n3)l例例4 StrassenStrassen矩阵乘法矩阵乘法矩阵乘法矩阵乘法2.4 分治法的应用分治法的应用StrassenStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)没有改没有改进StrassenStrassen矩阵乘法矩阵乘法u改进:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改大的改进例例5 棋盘覆盖棋盘覆盖在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.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;/分割棋盘 /覆盖左上角子棋盘 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,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+s=t;/覆盖其余方格 chessBoard(tr+s,tc+s,tr+s,tc+s,s);复杂度分析复杂度分析T(n)=O(4k)渐进意义下的最优算法l例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)渐进意义下的最优算法2.4 分治法的应用分治法的应用合并排序合并排序算法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(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)&平均平均时间复复杂度：度：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 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,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个元素中最大、最小值的递归代码。