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

《算法设计与分析 分治算法基本思想》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法基本思想程序4-1-1折半搜索templateintBinarySearch(Ta[],constT&x,intn){//在数组a[0:n-1]中搜索x，数组中的元素满足a[0]<=a[1]<=…<=a[n-1]。//如果找到x，则返回所在位置（数组元素的下标），否则返回–1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=mi

2、ddle–1;}return–1;//未找到x}while的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行次。由于每次循环需耗时，因此在最坏情况下，总的时间复杂性为。折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比如n，很大的问题时，往往会想到将该问题分解。比如将这n个输入分成k个不同的子集。如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的方法称为分治法。一

3、般来说，被分解出来的子问题应与原问题具有相同的类型，这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情形，即将整个问题二分。以下用A[1:n]来表示n个输入，用DanC(p,q)表示处理输入为A[p:q]情况的问题。分治法控制流程DanC(p,q)globaln，A[1:n];integerm,p,q;//1£p£q£nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p£m

4、DanC(m+1,q));endifendDanC这里，Small(p,q)是一个布尔值函数，用以判断输入规模为q-p+1的问题是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问题解的函数G(p,q).而Divide(p,q)是分割函数，决定分割点，Combine(x,y)是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则DanC总的计算时间可用下面的递归关系来估计：（4.1.1）例4.1.1求n元数组中的最大和最小元素最容易想到的算法是直接比较算法：将数组的第1个元素分别赋给两个临时变量：fmax=A[1];fmin=A[1];然

5、后从数组的第2个元素A[2]开始直到第n个元素逐个与fmax和fmin比较，在每次比较中，如果A[i]>fmax，则用A[i]的值替换fmax的值；如果A[i]fmax,则用A[i]的值替换fmax的值

6、；否则才将A[i]与fmin比较，如果A[i]fmax。如果采用分治的思想，我们可以给出算法，其时间复杂性在最坏和平均用时均为3n/2-2:递归求最大最小值算法伪代码MaxMin（i,j,fmax,fmin）//A[1:n]是n个元素的数组，参数i，j//是整数，1≤i≤j≤n，使用该过程将数组A[i:j]中的最大最小元//分别赋给fmax和fmin。globaln,A[1:n]

7、;integeri,j;ifi=jthenfmax=fmin=A[i];//子数组A[i:j]中只有一个元素elseifi=j-1then//子数组A[i:j]中只有两个元素ifA[i]

8、ndMax