《算法分析-分治法ppt课件.pptx》由会员分享，可在线阅读，更多相关《算法分析-分治法ppt课件.pptx（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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+1,en
2、d); 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&j=end)if(arri=arrj) tempk+=arri+;elsetempk+=arrj+;while(i=mid) tempk+=arri+;while(j=end) tempk+=arrj+;for(i=begin;i=end;i+) arri=tempi;归并排序的执行过程归并排序的优化当n某个值，如16时，将归并排序替换为插入排序可
3、以对归并前的序列做一些分析，如改为自然归并排序快速排序 数组划分两个数组各自排序void QuickSort(int A,int left,int right) if (leftright) int p = Partition(A, left, right); QuickSort(A, left, p-1); QuickSort(A, p+1, right);快速排序：双端划分int partition(int*R，int i，int j)int pivot=Ri;while(ij)while( (i ij=pivot.key) j-; if(ij) Ri+=Rj; while(ij&Ri.k
4、ey=pivot.key) i+；if(i1时，运行时间分解如下：分解：仅仅是计算出子数组的中间位置，需要常量时间，D(n)=(1)；解决：递归地求解两个规模为n/2的子问题，时间为2T(n/2)；合并：MERGE过程的运行时间为C(n)=(n)。归并排序算法分析(1) if 1( )2 ( /2)( ) if 1nT nT nnn分治法的效率总结1n) 1 (1n)()/()(当当OnfbnaTnT大整数相乘问题设X和Y都是n位的大整数，存储一个数组中。现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。这种方法要作O(n2)
5、步运算才能求出乘积XY。长整数相乘：不好的分治法求解分治法划分图示AB长整数相乘：改进的分治法求解最近点对问题(Closed Pair)简单的优化思想分治思想继续搜索的范围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个）计算时间
6、复杂度实现中的其它问题什么时候递归调用结束？至少在有三个点的时候就应该结束划分（否则某一端无法计算最小值）如何对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 = FindShortPairD
7、C(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) maxL) maxL=L;if(|A|maxL) 递归访问Aif(|C|maxL） 递归访问B修改的划分算法增加两个变量，分别表示“=部分”的左边界和右边界如果遇到某个元素与相等的情况，就把该元素移动到边界上其它情况处理相同提高分治法效率的途径因此，提高分治算法的效率，主要有以下几个途径：减小需要求解的问题个数；如二分查找,大数乘法，Strassen矩阵相乘算法减小分解时间复杂度减小合并时间复杂度，如快速排序分治法的适用条件问题可以直接划分为很多同质的子问题，并且子问题的求解比原问题求解容易反例：最短路径分治法的适用条件如果问题可以分解为很多子问题，并且各个子问题之间不相互交叉反例：Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)分治法的适用条件存在某种办法，能够降低的求解、分解或合并复杂度分治法求解的一般思路首先查看能否根据问题规模直接划分成若干个规模大体相等的问题，并且合并操作数量级远低于直接求解