分治专题讲座.ppt

《分治专题讲座.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析第二讲分治目的分治法的思想分治算法的设计方法将递归算法改写成迭代算法的一般方法重点分治法的抽象控制策略针对问题的抽象控制策略实现难点将递归算法改写成迭代算法的一般方法和实现2.1基本策略一、求解大规模问题的复杂性二、化整为零、分而治之Pnp1n1p2n2pknks0s1skS分解分治合并三、分治法的抽象控制策略设：原问题输入为a[n]，简记为(1，n)；子问题输入为a[p]~a[q]，1≤p≤q≤n，简记为(p，q)。已知：SOLUTION;intdivide(int,int);intsmall(i

2、nt,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是否在表中出现,若找到,返回其下标值,否则,返回一

3、负数.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(qa[k]

4、)returnBinSearch1(k+1,q,x);}三、递归算法四、计算复杂度1.二元比较树以有序表的中间元素为根节点的二分树左子树上所有元素不比父节点元素值大右子树上所有元素不比父节点元素值小527136849圆形接点称为内节点,对应成功检索的数据元素二分检索树的深度:二元比较树的深度:<11~22~33~44~55~66~77~88~9>9方形接点称为外节点,对应不成功检索的数据子集定理2.2若n在区域[2k-1,2k)中,则对于一次成功的检索,BinSearch1至多作k次比较;而对于一次不成功的检索,

5、或者作k-1次比较或者作k次比较。成功检索最好情况:不成功检索最好情况:成功检索最坏情况:不成功检索最坏情况:2.时间复杂度平均情况分析内部路径长度之和：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(log

6、n)O(logn)二分检索的时间复杂度结论定理2.3设a[n]含有n(n≥1)个不同元素,排序为a[1]<…

7、大和最小元素.一、问题二、直接搜索StraitSearch(n,&max,&min){*max=*min=a[0];for(i=1;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)直接搜索的改

8、进方法三、实现分治的递归算法集合只有一个元素时*max=*min=a[i]；集合只有两个元素时if(a[i]