算法分析与设计[分治法].pptVIP

西南科技大学计算机学院软件教研室 算法分析与设计 第二章 分治法 第二章 分治法 什么是分治法？ 二分检索 找最大和最小元素 归并分类 快速分类 选择问题 斯特拉森矩阵乘法 2.1 分治法的一般方法 分治策略DANDC的抽象化控制 Procedure DANDC(p,q) global n,A(1:n);integer m,p,q; //1≤p≤q≤n// if SMALL(p,q) then return(G(p,q)) else m?DIVIDE(p,q) //p≤m≤q// return(COMBINE(DANDC(p,m),DANDC(m+1,q))) endif End DANDC 分治策略DANDC的计算时间 倘若所分成的两个子问题的输入规模大致相等，则分治策略DANDC的计算时间可表示为： T(n)= 2.2 二分检索 问题描述 已知一个按非降次序排列的元素表a1,a2,…,an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并置于j，否则，置j为0。 一般解决方法（从头到尾查找一遍） 二分检索原理 将问题表示为：I=(n,a1,…,an,x) 选取一个下标k，可得到三个子问题： I1=(k-1,a1,…,ak-1,x) I2=(1,ak,x) I3=(n-k,ak+1,…,an,x) 如果对所求解的问题（或子问题）所选的下标k都是中间元素的下标，k=[(n+1)/2]，则由此产生的算法就是二分检索算法。 二分检索算法 Procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low?1;high?n if(n0) while （low≤high） do { mid?[(low+high)/2] /*取中间值*/ case xA[mid]: high?mid-1 /*寻找前一半*/ xA[mid]: low?mid+1 /*寻找后一半*/ else: j?mid ;return /*检索成功*/ endcase } j?0 /*检索失败*/ End BINSRCH 二分检索算法实例 假设在数组A(1:9)中顺序放了以下9个元素： -15 , -6 , 0 , 7 , 9 , 23 , 54 , 82 , 101 要求检索的x分别为：101 , -14 , 82 二分检索算法正确性的证明 用五个特性判断是否是一个算法 根据算法的描述，满足五个特性的才是算法 证明算法是否正确 如果n=0，则不进入循环，j=0，算法终止 否则就会进入循环与数组A中的元素进行比较 如果x=A[mid]，则j=mid，检索成功，算法终止 否则，若xA(mid)，则缩小到A(low)和A(mid-1)之间检索 若xA(mid)，则缩小到A(mid+1)和A(n)之间检索 按上述方式缩小检索区总可以在有限步内使lowhigh 如果出现这种情况，说明x不在A中，j=0，算法终止 二分检索算法所需的空间和时间 所需空间 用n个位置存放数组A，还有low,high,mid,x,j五个变量需要存储，共需空间n+5 计算时间 对于计算时间，需要分别考虑以下几种情况： 成功检索的最好情况和不成功检索的最好情况 成功检索的平均情况和不成功检索的平均情况 成功检索的最坏情况和不成功检索的最坏情况 成功检索最好情况和不成功检索最好情况 成功的检索共有n种 不成功的检索共有n+1种 二元比较树 二分检索的时间复杂度 定理2.2 ：若n在区域[2k-1,2k)中，则对于一次成功的检索，二分检索至多作k次比较，至少作1次比较；而对于一次不成功的检索，或者作k-1次比较或者作k次比较。 二分检索的时间复杂度 最坏情况下的成功检索计算时间Θ(logn) 最坏情况下的不成功检索计算时间Θ(logn) 最好情况下的成功检索计算时间Θ(1) 最好情况下的不成功检索计算时间Θ(logn) 每种不成功的检索时间都为Θ(logn) 成功检索的平均比较次数 由根到所有内部结点的距离之和称为内部路径长度I; 由根到所有外部结点的距离之和称为外部路径长度E; E=I+2n 令S(n)是成功检索的平均比较次数。 找一个内部结点表示的元素所需的比较次数是由根到该结点的路径长度（即距离）加1。因此，S(n)=I/n+1 到一个外部结点所需要的比较数是由根到该结点路径的长度。因此，U(n)=E/(n+1) 由以上各公式可得 S(n)=(1+1/n)U(n