第二讲-分治专题讲座

算法设计与分析第二讲分治目的分治法的思想分治算法的设计方法将递归算法改写成迭代算法的一般方法重点分治法的抽象控制策略针对问题的抽象控制策略实现难点将递归算法改写成迭代算法的一般方法和实现2.1基本策略一、求解大规模问题的复杂性二、化整为零、分而治之Pnp1n1p2n2pknks0s1skS分解分治合并三、分治法的抽象控制策略设：原问题输入为a[n]，简记为(1，n)；子问题输入为a[p]~a[q]，1≤p≤q≤n，简记为(p，q)。已知：SOLUTION;intdivide(int,int);intsmall(int,int);SOLUTIONconquer(int,int);SOLUTIONcombine(SOLUTION,SOLUTION);SOLUTIONDandC(p,q)/*divideandconquer*/{if(small(p,q))returnconquer(p,q);else{m=divide(p,q);returncombine(DandC(p,m),DandC(m+1,q));}}分治法的抽象控制算法已知n个按非降次序排列的元素a[n],查找元素x是否在表中出现,若找到,返回其下标值,否则,返回一负数.2.2二分检索一、问题二、分治的思路原问题:(n,a[0],…,a[n-1],x)数据分组:a[0]~a[k-2]a[k-1]a[k]~a[n-1]三个子问题:(k-1,a[0],…,a[k-2],x)(1,a[k-1],x)(n-k,a[k],…,a[n-1],x)intBinSearch1(p,q,x){intk=(p+q)/2;if(qp)return–1;/*参数错误*/if(x==a[k])returnk;if(xa[k])returnBinSearch1(p,k-1,x);if(xa[k])returnBinSearch1(k+1,q,x);}三、递归算法四、计算复杂度1.二元比较树以有序表的中间元素为根节点的二分树左子树上所有元素不比父节点元素值大右子树上所有元素不比父节点元素值小527136849圆形接点称为内节点,对应成功检索的数据元素二分检索树的深度:1nlog二元比较树的深度:2nlog11~22~33~44~55~66~77~88~99方形接点称为外节点,对应不成功检索的数据子集定理2.2若n在区域[2k-1,2k)中,则对于一次成功的检索,BinSearch1至多作k次比较;而对于一次不成功的检索,或者作k-1次比较或者作k次比较。(1)(log)(log)OkOnOn()(logn1)(log)OkOOn()(logn1)(log)OkOOn成功检索最好情况:不成功检索最好情况:成功检索最坏情况:不成功检索最坏情况:)1(O2.时间复杂度平均情况分析内部路径长度之和：I527136849外部路径长度之和：E,E=I+2n。成功检索的平均比较次数：S(n)=(I/n)+1不成功检索的平均比较次数:U(n)=E/(n+1)因为：U(n)=O(logn)，所以：S(n)=O(logn)由此可得：S(n)=(1+1/n)U(n)-1成功检索不成功检索最好最坏平均最好最坏平均O(1)O(logn)O(logn)O(logn)O(logn)O(logn)二分检索的时间复杂度结论定理2.3设a[n]含有n(n≥1)个不同元素,排序为a[1]…a[n].又设用以比较为基础去判断是否x∈a[n]的任何算法在最坏情况下所需的最小比较次数为FIND(n),那么,FIND(n)。)1log(n说明：任何以比较为基础的检索算法,最坏情况下的比较次数都不可能低于O(logn),因此,二分检索是最优的最坏情况算法。3.以比较为基础检索的时间下界思考题：1.请证明E=I+2n2.请证明S(n)=(I/n)+12.3找最大和最小元素在n个不同元素的集合a[n]中同时找出它的最大和最小元素.一、问题二、直接搜索StraitSearch(n,&max,&min){*max=*min=a[0];for(i=1;in;i++)/*语句1*/{if(a[i]*max)*max=a[i];if(a[i]*min)*min=a[i];}}比较次数：2(n-1)将语句1的体改写成if(a[i]*max)*max=a[i];elseif(a[i]*min)*min=a[i];最好情况：最坏情况：平均情况：n-12(n-1)3/2(n-1)由此可见,直接搜索的时间复杂度为:O(n)直接搜索的改进方法三、实现分治的递归算法集合只有一个元素时*max=*min=a[i]；集合只有两个元素时if(a[i]a[j]){*max=a[j];*min=a[i];}else{*max=a[i];*min=a[j];}集合中有更多元素时分治:将原集合分解成两个子集,分别求两个子集的最大和最小元素,再合并结果。递归算法typedefstruct{ElemTypemax,min;}SOLUTION;SOLUTIONMaxMin(i,j){SOLUTIONs,s1,s2;if(i==j){s.max=s.min=a[i];returns;}if(i==j-1){if(a[i]a[j]){s.max=a[j];s.min=a[i];}else{s.max=a[i];s.min=a[j];}returns;}k=(i+j)/2;s1=MaxMin(i,k);s2=MaxMin(k+1,j);(s1.max=s2.max)?(s.max=s1.max):(s.max=s2.max);(s1.min=s2.min)?(s.min=s1.min):(s.min=s2.min);returns;}时间复杂度2212)2/()2/(10)(nnnntntnt当n是2的幂时,即对于某个正整数k,n=2k,有112kii令t(n)表示MaxMin需要的元素比较次数,存在下列递推关系t(n)=2t(n/2)+2=2(2t(n/4)+2)+2=4t(n/4)+4+2=2k-1t(2)+=2k-1+2k-2=3n/2-2当元素的比较开销与整数比较开销相当时,将前两条if语句合并为：if(i=j-1)/*对应一元素和两元素的情况*/{if(a[i]a[j]){s.max=a[j];s.min=a[i];}else{s.max=a[i];s.min=a[j];}returns;}22()5/232(/2)32ncnncnnMaxMin需要的比较次数,存在下列递推关系：思考题请分析c(n)递推关系式中为什么是加3而不是加2?给定一个含n个元素的集合a[n],按一定次序(本课程假定均为非降次序)将其分类(排序)。2.4分类一、问题二、插入分类基本思想已分类的部分未分类的部分a[1]…a[j-1]a[j]a[j+1]…a[n]InsertSort(intn){for(j=1;jn;j++){for(unsorted=a[j],k=j-1;(k=0)&&(unsorteda[k]);k--)a[k+1]=a[k];a[k+1]=unsorted;}}插入分类算法考虑内层for循环中元素比较的次数T(n)最好情况：最坏情况：T(n)=O(n)T(n)==1+2+…n-1==O(n2)时间复杂度三、归并分类基本思想a[l]…a[]a[]…a[h]归并分类归并分类按非降次序合并两个已分类的子集2lh2lh归并分类递归算法MergeSort(l,h){if(lh){m=(l+h)/2;MergeSort(l,m);MergeSort(m+1,h);Merge(l,m,h);}}已分类子集的归并过程A1345691027811121314指针l=1,h=8,k=1B1指针l=2,h=8,k=2B12指针l=2,h=9,k=3B123456指针l=5,h=9,k=7B12345678指针l=5,h=11,k=9B12345678910指针l=8,h=11,k=11B1234567891011121314指针l=8,h=15,k=15Merge(low,mid,high){ElemTypeb[n];l=low;h=mid+1;k=l;while((l=mid)&&(h=high))/*部分合并*/{if(a[l]=a[h])b[k++]=a[l++];elseb[k++]=a[h++];}if(lmid)while(h=high)b[k++]=a[h++];/*转储剩余部分*/elsewhile(l=mid)b[k++]=a[l++];a[low:high]=b[low:high];/*将b数组转储到a*/}已分类子集的归并算法时间复杂度kn21,()2(/2)1,(log)anaTnTncnncOnn为常数是常数缺点与改进结合插入分类与归并分类各自的优点四、快速分类设计思路a[1]…a[j-1]a[j]a[j+1]…a[n]使a[1:j-1]≤a[j]a[j]使a[j+1:n]≥a[j]对a[1:j-1]快速分类a[j]对a[j+1:n]快速分类已分类的集合实现部分分类的划分过程举例原始41362578指针r=4jk一次循环r=4jkr=41326578二次循环kj交换位置213r=46578返回交换位置k实现部分分类的划分算法Partition(p,q){r=a[p];j=p+1;k=q;while(1){while((j=k)&&(a[j]=r))j++;while((j=k)&&(a[k]=r))k--;if(jk){t=a[j];a[j]=a[k];a[k]=t;j++;k--;}elsebreak;}a[p]=a[k];a[k]=r;returnk;}快速分类算法QuickSort(p,q){if(pq){j=Partition(p,q);QuickSort(p,j-1);QuickSort(j+1,q);}}时间复杂度最坏情况：CW(n)=n+n-1+…+3+2=O(n2).假设n个元素各不相同，划分元素随机选取，取第k(1≤k≤n)个元素是等概率的，计算时间C(n)取决于Partition的元素比较次数.平均情况：)()1(11)(1knCkCnnnCAnkAA经推导可得:CA(n)2(n+1)loge(n+1)=O(nlogn)结论：快速分类算法的最坏情况时间为O(n2),平均情况为O(nlogn).五、几种分类算法的时间复杂度比较插入分类归并分类快速分类最好O(n)最坏O(n2)O(nlogn)O(n2)平均O(nlogn)O(nlogn)结论：以比较为基础的分类算法在最坏情况下的时间下界为O(nlogn),是最坏情况下的最优算法。一、问题2.5选择给定一个含n个元素的集合a[n],找出其中第k小的元素，并将其转储到a[k]。二、最直观的求解算法按非降次序分类a[k]即为第k小的元素完全分类做了不必要的运算，效率低三、基于分治思想的选择算法原始a[1]…a[j-1]a[j]a[j+1]…a[n]partition使a[1:j-1]a[j]a[j]使a[j+1:n]a[j]分治kj,在a[1:j-1]中选择k=j结束kj,在a[j+1:n]中选择基本思路用partition算法实现分治selection(p,q,k){intj;j=partition(p,q);if(k==j)return;if(kj)selection(p,j-1,k);elseselection(j+1,q,k);}分治算法四、时间复杂度最坏情况：O(n2)最好，平均情况：O(n)思考题：1.过程MergeSort的时间复杂度是以什么计算操作频数度量的,最好情况、最坏情况、平均时间复杂度是多少?2.用C语言实现merg