第二章 分治法.ppt

第4章 分治法 —— “分”而治之 主要内容 一般方法 二分检索 找最大和最小元素 归并分类 快速分类 选择问题 斯特拉森矩阵乘法 3.1 一般方法 对大规模问题的求解 利用分治法求解大规模问题 2. 分治策略的抽象化控制 算法3.1 分治策略的抽象化控制 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 注： k=2: 二分是最常用的分解策略； SMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小而无需再进一步分就可求解； G(p,q)：对输入规模为q-p+1的子问题求解（SMALL(p,q)为真时）； DIVIDE(p.q)：对输入规模为q-p+1的子问题进一步分解，返回值为[p,q]区间进一步的分割点（SMALL(p,q)为假时； COMBINE(x,y)：子结果的合并函数，将区间[p,m]和[m+1,q]上的子问题的解合并成上级区间[p,q]上的“较完整”的解。当p=1,q=n时，就得到整个问题的解。 DANDC的计算时间 若所分成的两个子问题的输入规模大致相等，则DANDC总的计算时间可用递归关系式表示，如下： g(n) n足够小 T(n) = 2T(n/2) + f(n) 否则 分治法的另一种模型表示 proc dividandconquer(n) if n=n0 then g(n) else { divid n into small suninstances n1 n2 n3…nk for i=1 to k do yi=dividandconquer(ni) return merge(y1…yk) } end dividandconquer 进一步思考 n0选择多大合适？ 原问题应该分解成几个子问题？ 大量实践得出子问题的规模大致相当分治的效率较好。 一般进行2分法。 3.2 二分检索（折半查找） 1. 问题的描述 已知一个按非降次序排列的元素表a1, a2, …,an,判定某给定的元素x是否在该表中出现。 若是，则找出x在表中的位置并返回其所在下标 若非，则返回0值。 分治求解策略分析： 定义问题的形式描述：I=(n, a1, a2, …,an,x) 问题分解：选取下标k，由此将I分解为3个子问题： I1=(k-1, a1, a2, …,ak-1,x) I2=(1, ak,x) I3=(n-k, ak+1, ak+2, …,an,x) 对于I2，若ak=x，则有解k，对I1、I3不用再求解；否则， 若xak，则只在I1中求解，对I3不用求解； 若xak，则只在I3中求解，对I1不用求解； I1 、I3上的求解可再次采用分治方法划分后求解（递归过程） k的不同选择策略导致不同的检索算法：二分检索，Fibonacci检索，线性插值检索，随机检索。 2. 二分检索算法 算法3.3 二分检索 procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1; high←n; while low≤high do mid ← case :xA(mid):high←mid-1 :xA(mid):low ←m