算法设计与分析 课件 第三章 分治法

计算机算法设计与分析第三章

分治法学习目标掌握分治法的基本思想掌握分治法的特点和基本框架掌握分治法解决实际问题3.1分治法基本思想孙子兵法兵势篇曰：凡治众如治寡，分数是也。其大致意思就是管理大规模部队和管理小股部队是一样的，分开治理就是了。这就是分治法在军事上的运用。分治法的基本思想就是将一个较难以解决的规模大的问题，分割成多个相似的规模较小的子问题，先求出小规模子问题的解，然后将各小规模子问题的解组合起来就是规模大的问题的解。其中的一个关键点是分割的子问题一定要相似，这样就可以采取同样的方法来求解，从而将问题简化。例3.1

二分查找问题。在一个升序的含n个元素的数组a[]中查找x，输出x在数组a中的下标位置，若没查到返回-1。分析：可以考虑使用分治思想来解决，具体做法是设计三个变量left，mid和right将整个数组分成3个部分a[left,mid-1],a[mid],a[mid+1,right]。如果a[mid]>x，则使用相同的办法在较小范围[left,mid-1]中查找；如果a[mid]=x，则已查找到，返回mid即可；如果a[mid]<x，则使用相同的办法在较小范围[mid+1,right]中查找。以上过程都没查找到的话，则数组中不存在x，返回-1。3.1分治法基本思想例3.2

二分归并排序。将含有n个元素的数组a[]按关键字大小升序排列。以数组a[8]={8,4,5,7,1,3,6,2}为例来分析。3.1分治法基本思想3.2分治法的特点和基本框架当采用分治法时，一般原问题都需要具备以下几个特征：（1）难度递降：即原问题的解决难度，随着数据的规模的缩小而降低，当降低到一定程度时，问题很容易解决。（2）问题可分：原问题可以分解为若干个规模较小的同类型问题，即该问题具有最优子结构性质。这是应用分治法的前提。（3）解可合并：利用所有子问题的解，可合并出原问题的解。这个特征很关键，能否利用分治法完全取决于这个特征。（4）相互独立：各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题。如果子问题之间不独立，则分治法需要重复地解决公共的子问题，造成效率低下的结果。设P是要求解的问题，|P|为问题P的输入规模，现将分治法求解问题的基本框架描述如下：Divide-and-Conquer(P)：if|P|≤cthenS(P)

//当问题规模较小时，很容易求出解endifdividePintoP1,P2,...,Pk//将原问题分割为规模小的子问题fori=1tokdoxi=Divide-and-Conquer(Pi)//递归求解每个子问题endforreturnMerge(x1,x2,...,xk)//将子问题的解合并成原问题的解3.2分治法的特点和基本框架3.3分治法的时间复杂度分析分治法的实现一般都是采用递归算法。分析分治法的时间复杂度需要使用其递推公式来推导。分治法中通常的递推方程有以下两种类型：第一类是归约后子问题规模比原问题规模呈常数级减少。递推方程为如Hanoi塔问题使用分治法，将n个圆盘的问移动题归约为两个n-1圆盘移动子问题，也就是归约后的子问题规模只比原问题规模少1。递推方程为解得：第二类是归约后子问题规模比原问题规模呈倍数减少。该算法的时间复杂度可以通过以下递推公式求出：根据1.4.4节介绍的MasterTheorem主定理结论可知：3.3分治法的时间复杂度分析3.4.1分治法的典型实例——快速排序快速排序是数据结构中经典且高效的一种排序算法，它在实践中应用非常广泛。设待排的数组为A，快速排序的基本思想为：用数组的首元素作为标准将A划分为前、后两部分，前部分元素都比首元素小，后部分元素都比首元素大，这两部分就构成两个新的子问题。算法接着分别对这两部分递归地进行排序，各子问题排序完成后自然整个数组也就排序完成。算法的关键在于怎样划分数组A而将其归约成两个相同结构的子问题。3.4.1分治法的典型实例——快速排序快速排序算法Quicksort(A,p,r) //p和r分别为数组A的首元素和尾元素的下标输入：数组A[p..r],1≤p≤r≤n输出：从A[p]到A[r]按照升序排好序的数组Aifp<rthenq←Partition(A,p,r) //划分数组，找到首元素A[p]在排好序后的位置qA[p]↔A[q] //交换A[p]，A[q]中元素的值Quicksort(A,p,q-1) //对前部分继续递归地用快速排序算法Quicksort(A,q+1,r) //对后部分继续递归地用快速排序算法endif其算法中的Partition函数是划分的过程函数，它实现的就是以A[p..r]的首元素A[p]作为标准，输出q表示A[p]应该处在的正确位置，即排好序后A[p]应该放在数组下标为q的位置。过程如下：（1）先从后向前扫描数组A，找到第一个不大于A[p]的元素A[j]（2）从前向后扫描A找到第一个大于A[p]的元素A[i]（3）当i＜j时，交换A[i]与A[j]。这时A[j]后面的元素都大于A[p]，A[i]前面的元素都小于或等于A[p]。（4）接着对数组A从i到j之间的部分继续上面的扫描过程，直到i和j相遇，当i>j时，j就代表了A在排好序的数组中的正确位置q。此刻在q位置之前的元素都不大于A[p]，在q位置后面的元素都大于A[p]。3.4.1分治法的典型实例——快速排序3.4.1分治法的典型实例——快速排序划分算法Partition(A,p,r)输入：数组A[p..r],1≤p≤r≤n输出：数组首元素A[p]在排好序的数组中的位置x←A[p]i←pj←r+1whiletruedorepeatj←j-1untilA[j]≤x//从后往前找到不大于x的元素repeati←i+1untilA[i]>x//从前往后找到大于x的元素ifi<jthenA[i]↔A[j]//交换A[i]，A[j]中元素的值elsereturnj //i，j相遇，返回相遇的位置即为数组首元素A[p]的正确位置endifendwhile举例说明一趟划分的过程数组A[6]={64，57，86，42，12，53}，第一趟划分以64为标准，p=1i=2j=5交换A[2]和A[5]的值，继续循环。j=4i=5i<j不成立，一趟划分结束，返回值为4。在Quicksort中q=4,交换A[p]，A[q]中元素的值，就得到一次划分后的结果。在一趟快速排序结束后，继续对两个子数组{12,57,53,42}和{86}实施相同的操作。3.4.1分治法的典型实例——快速排序第1次循环645786421253第2次循环645753421286划分后1257534264863.4.2分治法的典型实例——大整数乘法1.问题描述采用分治法设计一个有效的算法，计算两个n位大整数的乘法。（n=2k,k=1,2,3....）。2.问题分析根据分治法的思想，可以将两个大的整数乘法分而治之。将大整数按位数的一半分成两个小整数，转换成稍简单的小整数乘法，再进行合并。上述的过程可以重复进行，直到得到最简单的两个1位数的乘法，从而解决上述问题。

3.4.2分治法的典型实例——大整数乘法3.4.2分治法的典型实例——大整数乘法3.算法设计BigIntMul(X,Y,n)输入：大整数X，Y和位数n输出：X与Y的乘积结果sx←sign(X),sy←sign(Y) //取X，Y的符号s←sx*sy //求出X×Y的符号ifs=0thenreturn0endifX←|X|,Y←|Y|ifn=1thenreturns*X*YendifA←X的左边n/2位, B←X的右边n/2位C←Y的左边n/2位, D←Y的右边n/2位m1←BigIntMul(A,C，n/2), m2←BigIntMul((A-B),(D-C)，n/2)m3←BigIntMul(B,D，n/2)S←m1*10^n+(m1+m2+m3)*10^(n/2)+m3returnS举例:以计算3141×5247为例来说明。将3141分拆成31和41，5247分拆成52和47。然后计算31×52，-10×-5，41×47。当出现两个数位数不等时，可以将位数小的高位补0再进行计算。如：-10×-5=10×05=(1×10+0)×(0×10+5)=1×0×100+(1×5+1×0+0×5)×10+0×5=0+50+0=50其他两个个同理算出：31×52=1612，41×47=1927。带入原来的算式得：3141×5247=16120000+(50+1612+1927)×100+1927=16480827。3.4.2分治法的典型实例——大整数乘法4.算法效率分析根据上述的计算过程得到递推方程。改进前：根据主定理理论可得：改进后：根据主定理可得：

，有较大的改进。3.4.3分治法的典型实例——平面内最近点问题

3.4.3分治法的典型实例——平面内最近点问题

2.问题分析如果采用蛮力法，就需要遍历平面上任意两个点之间的距离，然后比较得出最小的值。很显然其时间复杂度是O(n2)。那有没有更快的方法呢？考虑分治法，如图3.2所示，用一条垂直的直线l将整个平面中的点分为左半平面PL和右半平面PR两部分，使得两部分的点数近似相等。

3.4.3分治法的典型实例——平面内最近点问题将平面的点集一分为二PLPRP直线l

3.4.3分治法的典型实例——平面内最近点问题

3.4.4分治法的典型实例——选择第k小问题

大小S3S4S1S2中位数组M

3.4.3分治法的典型实例——平面内最近点问题平面上最临近点对算法MinDistance(P,X,Y)输入：n()个点集合P，X,Y分别表示n个点的x,y坐标的值输出：最近的两个点以及距离ifn≤

3then直接计算n个点之间的最短距离endifSort(n,X,Y) //把所有的点按照横坐标X排序

l←mid(X) //用一条竖直的线L将所有的点分成两等份MinDistance(PL,XL,YL)d1←PL中最短距离MinDistance(PR,XR,YR)d2←PR中最短距离d←min(d1,d2)while(PL中的点andXL≥l-d)dowhile(PR中的点andXR≤l+d)doifdistance(XL,YL,XR,YR)<dthen存储点对(XL,YL),(XR,YR)d←distance(XL,YL,XR,YR)endifendwhileendwhile该算法是递归算法，且里面有排序，为了提高效率，可以把排序操作放到递归算法的外面。另外在直线l两边距离不超过d的