算法设计与分析递归与分治.pptx
第二章 递归与分治2.1 分治法的基本思想2.2 分治法的适用条件2.3 分治法的基本步骤2.4 分治法的应用第1页/共39页2.1 分治法（divide-and-conquer）的基本思想为求解大问题，可以：分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。第2页/共39页将要求解的较大规模的问题分割成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个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。第3页/共39页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 分治法的基本思想第4页/共39页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 分治法的基本思想第5页/共39页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将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。第6页/共39页分治法的设计思想是，将一个难以直接解决的大分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。个击破，分而治之。2.1 分治法的基本思想第7页/共39页2.1 分治法的基本思想第8页/共39页2.2 分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构最优子结构性质性质利用该问题分解出的子问题的解可以合并为该问题的解；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。子问题。第9页/共39页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 分治法的应用第16页/共39页全排列算法void perm(int list,int k,int m)/产生listk.m的所有排列/其中list0.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);第17页/共39页l例3 二分搜索技术二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个个元素中找出一特定元素元素中找出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。2.4 分治法的应用第18页/共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 思考题：写出二分搜索的递归算法思考题：写出二分搜索的递归算法思考题：写出二分搜索的递归算法思考题：写出二分搜索的递归算法。l例3 二分搜索技术二分搜索技术2.4 分治法的应用第19页/共39页A和B的乘积矩阵C中的元素Ci,j定义为:u传统方法：O(n3)l例4 StrassenStrassen矩阵乘法矩阵乘法2.4 分治法的应用第20页/共39页StrassenStrassen矩阵乘法矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：u分治法:由此可得：复杂度分析复杂度分析T(n)=O(n3)没有改进没有改进第21页/共39页StrassenStrassen矩阵乘法矩阵乘法u改进:为了降低时间复杂度，必须减少乘法的次数。复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进第22页/共39页例5 棋盘覆盖棋盘覆盖在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.4 分治法的应用第23页/共39页棋盘覆盖棋盘覆盖当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。第24页/共39页棋盘覆盖棋盘覆盖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)渐进意义下的最优算法第25页/共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);/合并到数组b copy(a,b,left,right);/复制回数组a 复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法2.4 分治法的应用第26页/共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第27页/共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;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第28页/共39页非递归的归并排序算法(续)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;第29页/共39页合并排序合并排序&最坏时间复杂度：最坏时间复杂度：O(nlogn)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)&稳定性：稳定稳定性：稳定2.4 分治法的应用第30页/共39页2.4 分治法的应用给定线性序集中n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素例7 元素选择问题选择问题第31页/共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;return low;第32页/共39页随机划分：int randomizedPartition(int a,int p,int r)i=random(p,r);swap(ai,ap);return partition(a,p,r);快速排序快速排序中的划分中的划分(续续)第33页/共39页元素选择元素选择元素选择元素选择给定线性序集中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小元素第34页/共39页2.8 分治法求最大、最小问题分治法求最大、最小问题分治法求最大、最小问题分治法求最大、最小问题金块问题一老板有一袋金块，每月两名雇员因成绩优异被奖励，排名第一的雇员得最重的金块，排名第二的雇员得到最轻的金块。如有新的金块周期性地加到金袋中，则每月须找出最重、最轻的金块。设有台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。最大、最小问题实例第35页/共39页2.8 分治法求最大、最小问题分治法求最大、最小问题分治法求最大、最小问题分治法求最大、最小问题ABCDEFGabcdefgh第36页/共39页bool 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次第37页/共39页习题：写出二分搜索的递归算法写出求n个元素中最大、最小值的递归代码。第38页/共39页感谢您的观看！第39页/共39页
