计算机算法基础(第二章).ppt

第二章 分治法 —— “分”而治之 2.1 一般方法 对大规模问题的求解 利用分治法求解大规模问题 2. 分治策略的抽象化控制 算法2.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) 否则 注： T(n)：表示输入规模为n的DANDC计算时间 g(n)：表示对足够小的输入规模直接求解的计算时间 f(n)：表示COMBINE对两个子区间的子结果进行合并 的时间 （该公式针对具体问题有各种不同的变形） 2.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上的求解可再次采用分治方法划分后求解（递归过程） 2. 二分检索算法 算法2.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 ←mid+1 :else:j←mid;return endcase repeat j←0 end BINSRCH 例2.1：设A(1:9)=(-15，-6，0，7，9，23，54，82，101) 在A中检索x=101，-14，82。执行轨迹见下表1 3. 算法的正确性证明 定理2.1 过程BINSRCH(A,n,x,j)能正确运行 证明： 1）在具体指定A中的数据元素及x的数据类型后，算法中的所有运算都 能按要求正确运行——即首先满足确定性和能行性 2）终止性 算法初始部分置low←1, high←n ① 若n=0，不进入循环，j置0，算法终止