算法设计与分析-第四章-分治算法

1第四章分治算法§1.算法基本思想考虑下面折半搜索算法程序4-1-1折半搜索templateclassTintBinarySearch(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(xa[middle])left=middle+1;elseright=middle–1;}return–1;//未找到x}while的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行)(logn次。由于每次循环需耗时)1(，因此在最坏情况下，总的时间复杂性为)(logn。折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比如n，很大的问题时，往往会想到将该问题分解。比如将这n个输入分成k个不同的子集。如果能得到k个不同的可独立求解的子问题，而且在求出这些子问题的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型，这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情形，即将整个问题二分。以下用A[1:n]来表示n个输入，用DanC(p,q)表示处理输入为A[p:q]情况的问题。2分治法控制流程DanC(p,q)globaln，A[1:n];integerm,p,q;//1pqnifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//pmqreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC这里，Small(p,q)是一个布尔值函数，用以判断输入规模为q-p+1的问题是否小到无需进一步细分即可容易求解。若是，则调用能直接计算此规模下子问题解的函数G(p,q).而Divide(p,q)是分割函数，决定分割点，Combine(x,y)是解的合成函数。如果假定所分成的两个问题的输入规模大致相等，则DanC总的计算时间可用下面的递归关系来估计：用时是的用时算比较小时，直接求解运当输入规模CombinenfnfnTnGngnT)()()2/(2)(n)()(（4.1.1）例4.1.1求n元数组中的最大和最小元素最容易想到的算法是直接比较算法：将数组的第1个元素分别赋给两个临时变量：fmax=A[1];fmin=A[1];然后从数组的第2个元素A[2]开始直到第n个元素逐个与fmax和fmin比较，在每次比较中，如果A[i]fmax，则用A[i]的值替换fmax的值；如果A[i]fmin，则用A[i]的值替换fmin的值；否则保持fmax（fmin）的值不变。这样在程序结束时的fmax、fmin的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下的比较次数都是2(n-1)，而平均比较次数也是2(n-1)。如果将上面的比较过程修改为：从数组的第2个元素A[2]开始直到第n个元素，每个A[i]都是首先与fmax比较，如果A[i]fmax,则用A[i]的值替换fmax的值；否则才将A[i]与fmin比较，如果A[i]fmin，则用A[i]的值替换fmin的值。这样的算法在最好、最坏情况下使用的比较次数分别是n-1和2(n-1),而平均比较次数是3(n-1)/2,因为数组平均有一半的元素满足A[i]fmax。如果采用分治的思想，我们可以给出算法，其时间复杂性在最坏和平均用时均为3n/2-2:程序4-1-2递归求最大最小值算法伪代码MaxMin（i,j,fmax,fmin）//A[1:n]是n个元素的数组，参数i，j//是整数，1≤i≤j≤n，使用该过程将数组A[i:j]中的最大最小元//分别赋给fmax和fmin。3globaln,A[1:n];integeri,j;ifi=jthenfmax=fmin=A[i];\\子数组A[i:j]中只有一个元素elseifi=j-1then\\子数组A[i:j]中只有两个元素ifA[i]A[j]thenfmin=A[i];fmax=A[j]；elsefmin=A[j];fmax=A[i];endifelsemid=(i+j)/2;\\子数组A[i:j]中的元素多于两个MaxMin(i,mid,gmax,gmin);MaxMin(mid+1,j,hmax,hmin);fmax=max(gmax,hmax)；fmin=min(gmin,hmin)；endifendMaxmin如果用T(n)来表示MaxMin所用的元素比较数，则上述递归算法导出一个递归关系式：22)2/()2/(2110)(nnTnTnnnT(4.1.2)当n是2的方幂时，设kn2，有22/32222)2(224)4/(42)2)4/(2(22)2/(2)(1111nTnTnTnTnTkkkiik无论是最好、最坏、还是平均情况，MaxMin所用的比较数都是3n/2-2，比前面提到的算法(在最坏情况下)节省了25％的时间。实际上，任何一种以元素比较为基础的找最大最小元素的算法，其元素比较数的下界是22/3n。从这种意4义上来说，MaxMin算法是最优的。然而，由于需要1logn级的递归，每次递归调用需要将i，j，fmax，fmin和返回地址的值保留到栈中，所以需要多占用了内存空间。而且由于这些值出入栈时也会带来时间开销，特别当A中元素的比较次数和整数i与j的比较次数相差无几时，递归求最大最小值算法未必比直接求最大最小值算法效率高。例4.1.2．搜索算法的时间下界分析上节提到的折半搜索算法，我们已经知道其时间复杂度是)(lognO。事实上，我们可以用一个二元比较树来分析折半搜索算法的时间复杂性。以下是n=9的二元比较树：n＝9情况下折半搜索的二元比较树由图可见，当x在数组A中时，算法在圆形顶点结束；不在A中时，算法在方形顶点结束。因为43292，所以比较树的叶顶点都在4或5级上出现。因而元素比较的最多次数为4。一般地有：当kkn2,21时，一次成功的折半搜索至多做k次比较，而一次不成功的折半搜索或者做k-1次比较，或者做k次比较。现在假设数组A[1:n]满足：A[1]A[2]…A[n]。要搜索元素x是否在A中。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。任何以比较为基础的搜索算法的执行过程都可以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点（叶顶点）与之对应。线性搜索和折半搜索的二元比较树如下：9457613825定理4.1.1设数组A[1:n]的元素满足A[1]A[2]…A[n]。则以比较为基础，判断]:1[nAx的任何算法，在最坏情况下所需的最少比较次数Find(n)不小于log(n+1).证明通过考察模拟求解搜索问题的各种可能算法的比较树可知，Find(n)不大于树中由根到一个叶子的最长路径的距离。也就是说，在最坏情况下每种搜索算法的比较次数都是比较树中由根到叶顶点的最长距离。在所有的树中，这个最长距离以完全二叉树的最短。对于每个二叉比较树，必有n个内顶点与x在A中的n种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等于级数k，则最多有12k个内顶点。因此12kn，即Find(n)=klog(n+1)。证毕x:A[(n+1)/2]x:A[(n+1)/2]x:A[(n+1)/2]x:A[1]不成功不成功x:A[(n+1)/2-1]不成功不成功x:A[(n+1)/2+1]不成功不成功x:A[n]不成功不成功······················图4-1-2模拟折半搜索过程x:A[1]x:A[2]x:A[n]不成功不成功不成功不成功图4-1-1模拟线性搜索过程6由定理可见，任何一种以比较为基础的算法，其最坏情况下的所用时间不可能低于)(logn。因此，也就不可能存在其最坏情况下时间比折半搜索数量级（阶）还低的算法。事实上，折半搜索所产生的比较树的所有外部顶点都在相邻的两个级上，而且这样的二叉树使得由根到叶顶点的最长路径减至最小，因此，折半搜索是解决搜索问题在最坏情况下的最优算法。§2.关于排序算法问题：已知n个元素的数组A[1:n]，将A中元素按不降顺序排列。归并排序算法程序4-2-1向有序数组插入元素程序4-2-2插入排序templateclassTtemplateclassTvoidInsert(Ta[],int&n,constT&x)voidInsertionSort(Ta[],intn){//向数组a[0:n-1]中插入元素x{//对a[0:n-1]进行排序//假定a的大小超过nfor(inti=1;in;i++){inti;Tt=a[i];for(i=n-1;i=0&&xa[i];i--)Insert(a,i,t);a[i+1]=a[i];}a[i+1]=x;}n++;//添加了一个元素}将上述两个算法合并在一起，得到下述插入排序算法：程序4-2-3插入排序算法teplateclassTvoidInsertionSort(Ta[],intn)for(inti=1;in;i++){Tt=a[i];intj;for(j=i-1;j=0&&ta[j];j--)a[j+1]=a[j];a[j+1]=t;}}内层的for循环中的语句可能执行i次（i=1,…,n-1）,因此最坏情况的时间限7界是)(2/)1(211nnnjnj在这个算法中，大部分的时间都用在挪动元素上，随着已经排好顺序的数组的增长，被挪动的元素的个数也在增加，而且在整个过程中，很多元素不止一次被挪动。以下程序从某种程度上减少了这种浪费。这一算法的基本思想是采用，分治的方法，将要排序的数组分成两部分，先对每部分进行排序，然后再将两部分已经排好序的子数组的元素按照从小到大的顺序交替地摆放在一个新的数组中。这一过程也许需要多次分解和组合，因而是一个递归过程。程序4－2－4归并排序主程序伪代码MergeSort(low,high)//A[low:high]是一个全程数组，含有//high-low+1个待排序的元素。integerlow,high;iflowhighthenmid=(low+high)/2//求当前数组的分割点MergeSort(low,mid)//将第一子数组排序MergeSort(mid+1,high)//将第二子数组排序Merge(low,mid,high)//归并两个已经排序的子数组endifendMergeSort这里我们使用了辅助程序Merge:程序4-2-5合并过程伪代码Merge(low,mid,high)//已知全程数组A[low:high],其由两部分已经排\\好序的子数组构成：A[low:mid]和A[mid+1:high]。本程序的任务\\是将这两部分子数组合并成一个整体排好序的数组，再存于数组\\A[low:high].integerh,i,j,k,low,mid,high;globalA[low:high];localB[low:high];//借用临时数组Bh=low;i=low;j=mid+1;//h,j是拣取游标,i是存放游标whilehmid&&jhighdo