算法分析-分治法

算法分析与设计——分治法南阳理工学院软件学院胡吉兴分治法分治法的基本思想归并排序及其优化快速排序、众数问题分治算法分析分治法的基本思想将原问题分解为若干个同质但规模较小的子问题，各个子问题规模大致相同。对这些子问题分别进行求解(经常表现为递归调用)。对各个子问题的解进行合并，从而得到原问题的解。归并排序（合并排序）voidmergeSort(intarr[],inttemp[],intbegin,intend){intmid;if(beginend){mid=(begin+end)/2;mergeSort(arr,begin,mid);mergeSort(arr,mid+1,end);merge(arr,begin,mid,end);}}归并排序：有序表合并voidmerge(int*arr,int*temp,begin,mid,end){inti=begin,j=mid+1,k=begin;while(i=mid&&j=end){if(arr[i]=arr[j])temp[k++]=arr[i++];elsetemp[k++]=arr[j++];}while(i=mid)temp[k++]=arr[i++];while(j=end)temp[k++]=arr[j++];for(i=begin;i=end;i++)arr[i]=temp[i];}归并排序的执行过程归并排序的优化当n某个值，如16时，将归并排序替换为插入排序可以对归并前的序列做一些分析，如改为自然归并排序快速排序数组划分两个数组各自排序voidQuickSort(intA[],intleft,intright){if(leftright){intp=Partition(A,left,right);QuickSort(A,left,p-1);QuickSort(A,p+1,right);}}快速排序：双端划分intpartition(int*R，inti，intj){intpivot=R[i];while(ij){while(ij&&R[j].key=pivot.key)j--;if(ij)R[i++]=R[j];while(ij&&R[i].key=pivot.key)i++；if(ij)R[j--]=R[i];}R[i]=pivot;returni；}快速排序执行过程图11分治法递归式范式分治法的算法分析是典型的递归式求解的应用。其典型递归式如下：D(n)是把原问题分解为子问题所花的时间；C(n)是把子问题的解合并为原问题的解所花的时间；T(n)是一个规模为n的问题的运行时间。为简化算法分析，通常假设n为2的幂次，使得每次分解产生的子序列长度恰为n/2。这一假设并不影响递归式解的增长量级。(1)if()(/)()()otherwisencTnaTnbDnCn归并排序算法分析（）归并排序n个数最坏运行时间：当n=1时，归并一个元素的时间是个常量；当n1时，运行时间分解如下：分解：仅仅是计算出子数组的中间位置，需要常量时间，D(n)=Θ(1)；解决：递归地求解两个规模为n/2的子问题，时间为2T(n/2)；合并：MERGE过程的运行时间为C(n)=Θ(n)。归并排序算法分析求解该递归式，得𝑇𝑛=Θ(𝑛𝑙𝑜𝑔𝑛)(1)if1()2(/2)()if1nTnTnnn分治法的效率总结一般情况下，分治法的效率可以表示如下其中，f(n)为当问题规模为n时，分解问题和合并问题的总开销在该式中，时间复杂度与a、f(n)正相关，与b负相关，但真正决定时间复杂度的是𝑛log𝑏𝑎与f𝑛中数量级较大的一个1n)1(1n)()/()(当当OnfbnaTnT大整数相乘问题设X和Y都是n位的大整数，存储一个数组中。现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。这种方法要作O(n2)步运算才能求出乘积XY。长整数相乘：不好的分治法求解我们将n位的整数X和Y各分为2段，每段的长为n/2位由此，X=𝐴10𝑛2+𝐵，Y=𝐶10𝑛2+𝐷。于是，X和Y的乘积为：𝑋𝑌=𝐴10𝑛2+𝐵𝐶10𝑛2+𝐷=𝐴𝐶10𝑛+𝐴D+𝐵C10𝑛2+𝐵𝐷需要函数调用4次，若干个n位数的操作𝑇𝑛=4𝑇𝑛2+𝑐𝑛由此可得𝑇𝑛=Θ(𝑛2)分治法划分图示既然是一个n位整数，我们可以把它均分为两部分（首先前面加零补成2的整数次方位），如下图所示则𝑋=𝐴10n/2+B，于是可以将n位长整数相乘问题转换为n/2位长整数相乘问题AB长整数相乘：改进的分治法求解要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:𝑋𝑌=𝐴𝐶10𝑛+𝐴+𝐵𝐶+𝐷−𝐴𝐶−BD10n2+BD虽然，式(3)看起来比式(1)复杂些，但它仅需做3次函数调用因此𝑇𝑛=3𝑇𝑛2+𝑐𝑛用解递归方程的套用公式法马上可得其解为𝑇𝑛=Θ𝑛𝑙𝑜𝑔23=Θ𝑛1.59最近点对问题(ClosedPair)在一个二维空间中，有若干的点𝑣1𝑥1,𝑦1,𝑣2𝑥2,𝑦2…定义欧氏距离𝑑𝑣𝑖,𝑣𝑗=𝑥𝑖−𝑥𝑗2+𝑦𝑖−𝑦𝑗2求所有点中的距离最小的两个点简单的优化思想在计算欧氏距离时，不必开方如果已知最近距离为r，那么如果𝑥1−𝑥2≥𝑟或y1−y2≥𝑟，则不必进一步计算此两点距离如果进一步把各点按照x排序，则对所有𝑥−𝑥1≥𝑟的点不必计算距离分治思想按照一维预排序把数据集均分成两部分(能得到划分线l)分别对两部分求最近点距离𝑑1,𝑑2,令d=min(d1,d2)但是d不一定是最终问题的解，最小值可能还来自于一个点在左子集中一个点在右子集中，所以需要继续搜索继续搜索的范围x轴X=lX=l+dX=l-d区域L’记为左边区间（l-d=x=l）；右边区间记为R’枚举所有一个在L’，而另一个在R’中的点对，找到其中距离最近的一个区域R'区域L'区域R区域L对一个点P(x0,y0)来说，最多需要比较6个点x轴X=lX=l+dX=l-dY=y0+dY=y0-dP合并过程先把所有R’区域元素复制出来，并按照y坐标排序对每个L’区域的点P(x0,y0)，计算所有R’区域中y坐标为[y0-d,y0+d]的点（不会超过6个）计算时间复杂度合并的时间复杂度包括排序的时间复杂度和搜索的时间复杂度因为对于C1中每个点，至多只用在C中搜索6个点，所以总的搜索次数小于6n𝑇𝑛=2𝑇𝑛2+𝑐𝑛解得𝑇𝑛=Θ(𝑛𝑙𝑜𝑔𝑛)实现中的其它问题什么时候递归调用结束？至少在有三个点的时候就应该结束划分（否则某一端无法计算最小值）如何对Y坐标排序？代码doubleFindShortPairDC(constPoint*p,intnum)//DC代表divideandconquer，分治{if(num=3)//也许您认为，递归到2个点时，才应该返回距离。但如果为3个点，可能会出现PL有2个点，PR有1个点的情况，这时dR会无法计算，所以3个点就要蛮力计算返回。returnEnumShortestPair(p,num);mid=(num+1)/2;dL=FindShortPairDC(p,mid);dR=FindShortPairDC(p+mid,num-mid);s=min(dL,dR)for(i=0;istripPointNum;i++)for(j=i+1;jstripPointNum;j++)if(dist(pi,pj)s)s=dist(pi,pj);returns;}基于划分算法的分治——众数问题在很多数集的问题中，问题的分解需要伴随集合的划分如：快速选择问题众数问题众数问题给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。目标：对于给定的由n个自然数组成的多重集S，编程计算S的众数及其重数。众数问题众数问题无法使用简单的集合分解解决原因：如果直接将序列均分为两部分，可能元素A在左边有若干个，右边也有若干个，因此无法计数；左右子序列的众数，与整个序列的众数，没有必然关系解决众数问题的递归算法首先选择一个基准数，采用划分算法将集合分为三部分，小于该数的部分A，等于该数的部分B，大于该数的部分CL=|B|if(LmaxL)maxL=L;if(|A|maxL)递归访问Aif(|C|maxL）递归访问B修改的划分算法增加两个变量，分别表示“=部分”的左边界和右边界如果遇到某个元素与相等的情况，就把该元素移动到边界上其它情况处理相同提高分治法效率的途径因此，提高分治算法的效率，主要有以下几个途径：减小需要求解的问题个数；如二分查找,大数乘法，Strassen矩阵相乘算法减小分解时间复杂度减小合并时间复杂度，如快速排序分治法的适用条件问题可以直接划分为很多同质的子问题，并且子问题的求解比原问题求解容易反例：最短路径分治法的适用条件如果问题可以分解为很多子问题，并且各个子问题之间不相互交叉反例：Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)分治法的适用条件存在某种办法，能够降低的求解、分解或合并复杂度分治法求解的一般思路首先查看能否根据问题规模直接划分成若干个规模大体相等的问题，并且合并操作数量级远低于直接求解