中科院陈玉福算法讲义ch3

《中科院陈玉福算法讲义ch3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章分治算法47第三章分治算法§1.算法基本思想先来分析折半搜索算法程序3-1-1折半搜索procBiFind(a,n)//在数组a[1..n]中搜索x，数组中的元素满足a[1]≤a[2]≤…≤a[n]。//如果找到x，则返回所在位置（数组元素的下标），否则返回–1globala[1..n],n;integerleft,right,middle;left:=1;right:=n;whileleft≤rightdomiddle:=(left+right)/2;ifx=a[middle]thenreturn(m

2、iddle);end{if}ifx>a[middle]thenleft:=middle+1;elseright:=middle-1;end{if}end{while}return(–1);//未找到xend{BiFind}while的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行Θ(logn)次。由于每次循环需耗时Θ)1(，因此在最坏情况下，总的时间复杂度为Θ(logn)。折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比如n，很大的问题时，往往会想到将

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

4、1..n]来表示n个输入，用DiCo(p,q)表示用分治法处理输入为A[p..q]的问题。48第三章分治算法分治法控制流程procDiCo(p,q)globaln，A[1..n];integerm,p,q;//1≤p≤q≤nifSmall(p,q)thenreturn(Sol(p,q));elsem:=Divide(p,q);//p≤m

5、q-p+1的问题是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问题解的函数Sol(p,q).而Divide(p,q)是分割函数，决定分割点；Combine(x,y)是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则DiCo总的计算时间可用下面的递归关系来估计：⎧gn(),当输入规模比较小时直接求解nSol()n的用时Tn()=⎨（3.1.1）⎩2(/2)Tn+fn(),fnCombine()是用时例3.1.1求n元数组中的最大和最小元素最容易想到的算法是直接比较算法：将数组的

6、第1个元素分别赋给两个临时变量：fmax:=A[1];fmin:=A[1];然后从数组的第2个元素A[2]开始直到第n个元素逐个与fmax和fmin比较，在每次比较中，如果A[i]>fmax，则用A[i]的值替换fmax的值；如果A[i]

7、数组的第2个元素A[2]开始直到第n个元素，每个A[i]都是首先与fmax比较，如果A[i]>fmax,则用A[i]的值替换fmax的值；否则才将A[i]与fmin比较，如果A[i]fmax情况。如果采用分治的思想，可以构造算法，其时间复杂度在最坏情况下和平均用时均为3n/2-2:第三章分治算法49程序3-1-2递归

8、求最大最小值算法伪代码procMaxMin（i,j,fmax,fmin）//A[1:n]是n个元素的数组，参数i，j//是整数，1≤i≤j≤n，使用该过程将数组A[i..j]中的最大最小元//分别赋给fmax和fmin。globaln,A[1..n];integeri,j;ifi=jthenfmax:=A[i];fmin:=A[i];//子数组A[i..j]中只有一个元素elifi=j-1then/