算法分析-分治法ppt课件.pptx

《算法分析-分治法ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计——分治法南阳理工学院软件学院胡吉兴分治法分治法的基本思想归并排序及其优化快速排序、众数问题分治算法分析分治法的基本思想将原问题分解为若干个同质但规模较小的子问题，各个子问题规模大致相同。对这些子问题分别进行求解(经常表现为递归调用)。对各个子问题的解进行合并，从而得到原问题的解。归并排序（合并排序）voidmergeSort(intarr[],inttemp[],intbegin,intend){intmid;if(begin

2、nd);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

3、];}归并排序的执行过程归并排序的优化当n<某个值，如16时，将归并排序替换为插入排序可以对归并前的序列做一些分析，如改为自然归并排序快速排序数组划分两个数组各自排序voidQuickSort(intA[],intleft,intright){if(left

4、.key>=pivot.key)j--;if(i

5、析（）归并排序n个数最坏运行时间：当n=1时，归并一个元素的时间是个常量；当n>1时，运行时间分解如下：分解：仅仅是计算出子数组的中间位置，需要常量时间，D(n)=Θ(1)；解决：递归地求解两个规模为n/2的子问题，时间为2T(n/2)；合并：MERGE过程的运行时间为C(n)=Θ(n)。归并排序算法分析分治法的效率总结大整数相乘问题设X和Y都是n位的大整数，存储一个数组中。现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。这种方法要作O(n2)步运算才能求出乘积XY。长整数相乘：不好的分治法求解分治法划分图示A

6、B长整数相乘：改进的分治法求解最近点对问题(ClosedPair)简单的优化思想分治思想继续搜索的范围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个）计算时间复杂度实现中的其它问题什么时候

7、递归调用结束？至少在有三个点的时候就应该结束划分（否则某一端无法计算最小值）如何对Y坐标排序？代码doubleFindShortPairDC(constPoint*p,intnum)  //DC代表divideandconquer，分治{if(num<=3)//也许您认为，递归到2个点时，才应该返回距离。但如果为3个点，可能会出现PL有2个点，PR有1个点的情况，这时dR会无法计算，所以3个点就要蛮力计算返回。returnEnumShortestPair(p,num);mid=(