算法设计与分析分治算法基本思想

1、算法基本思想程序4-1-1折半搜索tempi atevciass Tint Bin arySearch(T a, const T& x, int n)an-1。/在数组a0:n-1中搜索x，数组中的元素满足&0=&1=amiddle) left=middle+1;else right=middle - 1;return - 1; / 未找到 xwhile的每次循环(最后一次除外)都将以减半的比例缩小搜索范围， 所以, 该循环在最坏的情况下需要执行 (log n)次。由于每次循环需耗时0(1)，因此在最坏情况下，总的时间复杂性为O(log n)。折半搜索算法贯彻一个思想，即分治法。当人们要解决一

2、个输入规模，比 如n,很大的问题时，往往会想到将该问题分解。比如将这 n个输入分成k个不 同的子集。如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题 的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型， 这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情 形，即将整个问题二分。以下用A1:n来表示n个输入，用DanC(p,q)表示处

3、理 输入为Ap:q情况的问题。分治法控制流程DanCp ,q)global n，A1:n;integer m,p,q; / 1兰p兰nif Small( p,q)the n return G(p ,q);else m=Divide(p,q); / p兰mvqreturn Comb in e(Da nC(p ,m),Da nC(m+1,q);en difend DanC这里，Small(p,q)是一个布尔值函数，用以判断输入规模为_q-p+1的问题 是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问 题解的函数 G( p,q).而Divide( p,q)是分割函数，决定分割点

4、，Comb in e(x,y)是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则Dane总的计算时间可用下面的递归关系来估计：fg(n)当输入规模n比较小时，直接求解运 算G(n)的用时T(n) i2T( n/2) + f(n) f(n)是 Combi ne用时(例4.1.1求n元数组中的最大和最小元素最容易想到的算法是直接比较算法：将数组的第1个元素分别赋给两个临时 变量：fmax=A1; fmin=A1;然后从数组的第2个元素A2开始直到第n个元素逐个与fmax和fmin比较，在每次比较中，如果 Ai fmax ，则用Ai 的值替换fmax的值；如果Ai fmax,则用Ai的值

5、替换 的值；否则才将Ai与fmin比较，如果Ai 的值。这样的算法在最好、 平均比较次数是3(n-1)/2,如果采用分治的思想， 均为 3n/2-2:n个fmaxfminfmax。我们可以给出算法，其时间复杂性在最坏和平均用时递归求最大最小值算法伪代码MaxMin( i,j,fmax,fmin )/A1:n 是 n 个元素的数组，参数 i ， j/是整数，Ki j n,使用该过程将数组Ai:j中的最大最小元 /分别赋给fmax和fmin。global n, A1: n; in teger i, j;if i=j the nfmax=fmi n=Ai; /elseif i=j-1if AiAj子

6、数组Ai:j中只有一个元素 then /子数组Ai:j中只有两个元素the n;fmax=Aj；fmi n=Aielsefmi n=Aj;fmax=Ai;en difelse mid= L(i+j)/2 _ /子数组Ai:j 中的元素多于两个MaxM in (i, mid, gmax, gmin);MaxM in( mid+1, j, hmax, hmin); fmax=max(gmax, hmax)； fmi n=mai n( gmi n, hmi n)； en difend Maxm in如果用T(n)来表示MaxMin所用的元素比较数，则上述递归算法导出一个 递归关系式：T( n)=r(

7、Ln/2T(m/2l)+2n=1n = 2n2当n是2的方幕时，设n =2k ,有无论是最好、最坏、还是平均情况，MaxMin所用的比较数都是3n 12-2，比前面提到的算法（在最坏情况下）节省了 25%的时间。实际上，任何一种以元素比较为基础的找最大最小元素的算法，其元素比较数的下界是3n/2-2。从这种意义上来说，MaxMin算法是最优的。然而，由于需要log n+1级的递归，每次递归调用需要将i , j，fmax，fmin和返回地址的值保留到栈中，所以需要多占用 了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当A中元素的比较次数和整数i与j的比较次数相差无几时，递归求最大最小值

8、算法未必比直接 求最大最小值算法效率高。例4.1.2搜索算法的时间下界分析上节提到的折半搜索算法，我们已经知道其时间复杂度是O(log n)。事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。 n=9的二元比较树：以下是A中时，算法4或5级上出现。68士束；不在情况下折半扌索的二元比较树由图可见，当x在数组A中时，算法在圆形结在方形结点结束。因为2 9 22所以比较树的叶结点因而元素比较的最多次数为4o 般地有：当n亡2k-,2k )时，成功的折半搜索至 多做k次比较，而不成功的折半搜索或者做 k-1次比较，或者做k次比较。现在假设数组A1:n满足：A1 A2 An。要搜索元素x

9、是否在A中。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计 的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可 以用一棵二元比较树来描述。每次可能的比较用一个内结点表示，对应于不成功 的结果有一个外结点(叶结点)与之对应。线性搜索和折半搜索的二元比较树如 下：X: A1丿4d锐线性搜索过程模 ArIX:A2 r拟折半搜索过程不成功 A2 AML。则 _F所需的最少比较次门xtAnd(3n+1)/4 定理4.1.1设数组A1:n的元素满r上不成功基础，判断 A1: n的任何算法x：A在最坏情4况不小于log(n+1) 1.X . 不成功不成功证明通过考察模拟求解搜索问题的各种可能算法的比较树可矢取 不大于树中由根到一个叶子的最长路径的距离o+也就是说，在最坏 索算法的比较次数都是比到叶结点的 詩 k，坛个距离等于该 二叉树的总级数减1。对于每个二叉比较树，必有 个内结点|X在A中的 n种 可能的情况相对应。不一棵比较二叉树的所有内结点所在的级数成功都不会超过该二叉树的总级数减1o则最多有2k -1个内结点。因此n flog(n+1) Io证毕由定理可见，任何一种以