《算法分析分治法ppt课件.pptx》由会员分享，可在线阅读，更多相关《算法分析分治法ppt课件.pptx（37页珍藏版）》请在三一办公上搜索。
1、算法分析与设计分治法,南阳理工学院软件学院 胡吉兴,分治法,分治法的基本思想归并排序及其优化快速排序、众数问题分治算法分析,分治法的基本思想,将原问题分解为若干个同质但规模较小的子问题，各个子问题规模大致相同。对这些子问题分别进行求解(经常表现为递归调用)。对各个子问题的解进行合并，从而得到原问题的解。,归并排序（合并排序）,void mergeSort(int arr,int temp,int begin,int end) int mid; if(beginend) mid=(begin+end)/2; mergeSort(arr,begin,mid); mergeSort(arr,mid+
2、1,end); merge(arr,begin,mid,end); ,归并排序：有序表合并,void merge(int *arr,int *temp,begin,mid,end)int i=begin,j=mid+1,k=begin; while(i=mid,归并排序的执行过程,归并排序的优化,当n某个值，如16时，将归并排序替换为插入排序可以对归并前的序列做一些分析，如改为自然归并排序,快速排序,数组划分两个数组各自排序void QuickSort(int A,int left,int right) if (leftright) int p = Partition(A, left, rig
3、ht); QuickSort(A, left, p-1); QuickSort(A, p+1, right);,快速排序：双端划分,int partition(int*R，int i，int j)int pivot=Ri;while(i=pivot.key) j-; if(ij) Ri+=Rj; while(ijreturn i；,快速排序执行过程图,11,分治法递归式范式,分治法的算法分析是典型的递归式求解的应用。其典型递归式如下：D(n)是把原问题分解为子问题所花的时间；C(n)是把子问题的解合并为原问题的解所花的时间；T(n)是一个规模为n的问题的运行时间。为简化算法分析，通常假设n为2
4、的幂次，使得每次分解产生的子序列长度恰为n/2。这一假设并不影响递归式解的增长量级。,归并排序算法分析（）,归并排序n个数最坏运行时间：当n=1时，归并一个元素的时间是个常量；当n1时，运行时间分解如下：分解：仅仅是计算出子数组的中间位置，需要常量时间，D(n)=(1)；解决：递归地求解两个规模为n/2的子问题，时间为2T(n/2)；合并：MERGE过程的运行时间为C(n)=(n)。,归并排序算法分析,求解该递归式，得 =(),分治法的效率总结,一般情况下，分治法的效率可以表示如下其中，f(n)为当问题规模为n时，分解问题和合并问题的总开销在该式中，时间复杂度与a、f(n)正相关，与b负相关，
5、但真正决定时间复杂度的是 log 与f 中数量级较大的一个,大整数相乘问题,设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+C 10 2 +需要函数调用4次，若干个n位数的操作 =4 2 +由此可得 =( 2 ),分治法划分图示,既然
6、是一个n位整数，我们可以把它均分为两部分（首先前面加零补成2的整数次方位），如下图所示则= 10 n/2 +B，于是可以将n位长整数相乘问题转换为n/2位长整数相乘问题,A,B,长整数相乘：改进的分治法求解,要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:= 10 + + + BD 10 n 2 +BD虽然，式(3)看起来比式(1)复杂些，但它仅需做3次函数调用因此 =3 2 +用解递归方程的套用公式法马上可得其解为 = 2 3 = 1.59,最近点对问题(Closed Pair),在一个二维空间中，有若干的点 1 1 , 1 , 2 2 , 2 定义欧氏距离 , =
7、 2 + 2 求所有点中的距离最小的两个点,简单的优化思想,在计算欧氏距离时，不必开方如果已知最近距离为r，那么如果 1 2 或 y 1 y 2 ，则不必进一步计算此两点距离如果进一步把各点按照x排序，则对所有 1 的点不必计算距离,分治思想,按照一维预排序把数据集均分成两部分(能得到划分线l)分别对两部分求最近点距离 1 , 2 ,令d=min(d1,d2)但是d不一定是最终问题的解，最小值可能还来自于一个点在左子集中一个点在右子集中，所以需要继续搜索,继续搜索的范围,x轴,X=l,X=l+d,X=l-d,区域L记为左边区间（l-d=x=l）；右边区间记为R,枚举所有一个在L，而另一个在R中
8、的点对，找到其中距离最近的一个,区域R,区域L,区域R,区域L,对一个点P(x0,y0)来说，最多需要比较6个点,x轴,X=l,X=l+d,X=l-d,Y=y0+d,Y=y0-d,P,合并过程,先把所有R区域元素复制出来，并按照y坐标排序对每个L区域的点P(x0,y0)，计算所有R区域中y坐标为y0-d,y0+d的点（不会超过6个）计算,时间复杂度,合并的时间复杂度包括排序的时间复杂度和搜索的时间复杂度因为对于C1中每个点，至多只用在C中搜索6个点，所以总的搜索次数小于6n =2 2 +解得 =(),实现中的其它问题,什么时候递归调用结束？至少在有三个点的时候就应该结束划分（否则某一端无法计算
9、最小值）如何对Y坐标排序？,代码,double FindShortPairDC(const Point* p, int num) /DC代表divide and conquer，分治if (num = 3) /也许您认为，递归到2个点时，才应该返回距离。但如果为3个点，可能会出现PL有2个点，PR有1个点的情况，这时dR会无法计算，所以3个点就要蛮力计算返回。return EnumShortestPair(p, num); mid = (num+1)/2;dL = FindShortPairDC(p, mid);dR = FindShortPairDC(p+mid, num-mid);s=mi
10、n(dL, dR)for (i=0; istripPointNum; i+)for (j=i+1; jstripPointNum; j+) if (dist(pi, pj) s) s = dist(pi, pj);return s;,基于划分算法的分治众数问题,在很多数集的问题中，问题的分解需要伴随集合的划分如：快速选择问题众数问题,众数问题,给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=1，2，2，2，3，5。多重集S的众数是2，其重数为3。目标：对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。,众数问
11、题,众数问题无法使用简单的集合分解解决原因：如果直接将序列均分为两部分，可能元素A在左边有若干个，右边也有若干个，因此无法计数；左右子序列的众数，与整个序列的众数，没有必然关系,解决众数问题的递归算法,首先选择一个基准数，采用划分算法将集合分为三部分，小于该数的部分A，等于该数的部分B，大于该数的部分CL=|B|if(LmaxL) maxL=L;if(|A|maxL) 递归访问Aif(|C|maxL） 递归访问B,修改的划分算法,增加两个变量，分别表示“=部分”的左边界和右边界如果遇到某个元素与相等的情况，就把该元素移动到边界上其它情况处理相同,提高分治法效率的途径,因此，提高分治算法的效率，
12、主要有以下几个途径：减小需要求解的问题个数；如二分查找,大数乘法，Strassen矩阵相乘算法减小分解时间复杂度减小合并时间复杂度，如快速排序,分治法的适用条件,问题可以直接划分为很多同质的子问题，并且子问题的求解比原问题求解容易反例：最短路径,分治法的适用条件,如果问题可以分解为很多子问题，并且各个子问题之间不相互交叉反例：,Fib(5),Fib(4),Fib(3),Fib(3),Fib(2),Fib(2),Fib(1),Fib(2),Fib(1),分治法的适用条件,存在某种办法，能够降低的求解、分解或合并复杂度,分治法求解的一般思路,首先查看能否根据问题规模直接划分成若干个规模大体相等的问题，并且合并操作数量级远低于直接求解,
