分治（二）快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。voidQuickSort(inta[],intp,intr){if(p
x的元素交换到右边区域while(true){while(a[++i]x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}快速排序快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)templateintRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}大整数的乘法一般的整数：16位、32位、64位计算机硬件可直接处理——常数时间公钥加密方法RSA的提出大大推动了大整数算法的研究目前一般认为RSA需要1024位以上的字长才有安全保障大整数的乘法大整数——无法在计算机硬件能直接表示的整数范围内进行处理若用浮点表示则只能近似表示它的大小要得到所有位上的准确数字——软件方法用数组存储一个大整数编程实现两个大整数的乘法大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:X=Y=X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bdabcd复杂度分析T(n)=O(n2)没有改进大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd为了降低时间复杂度，必须减少乘法的次数。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。大整数的乘法请设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法??如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法。循环赛日程表设计一个满足以下
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。日程选手11221n=2时日程选手1231234214334124321n=4时日程选手12345671234567821436587341278564321876556781234658721437856341287654321n=8时当n不是2的整数幂时，若n为奇数，能在n天内完成循环赛，若n为偶数，能在n-1天内完成循环赛。请给出你的设计方案。讨论（3）日程选手12345123456234561345612456123561234612325棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。规模较小的情况n=2规模较小的情况n=4规模较小的情况n=4规模较小的情况n=8规模较小的情况n=8规模较大的情况当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。Strassen矩阵乘法A和B的乘积矩阵C中的元素C[i,j]定义为: 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)传统方法：O(n3)Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：传统方法：O(n3)分治法:由此可得：复杂度分析T(n)=O(n3)Strassen矩阵乘法传统方法：O(n3)分治法:为了降低时间复杂度，必须减少乘法的次数。复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进Strassen矩阵乘法传统方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？最接近点对问题设S是平面上n个点的集合，要在S内找到一对点（p,q），使其相互距离最短。蛮力算法：计算所有可能的n(n-1)/2个点对并返回最短间距的点对。时间复杂度：O(n2)本节将运用分治技术描述一个时间复杂度为Θ(nlogn)的算法最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。简单！排序后扫描一遍数组即可！用分治法：（1）划分：我们用x轴上某个点m将S划分为2个子集S1和S2；（2）治理：分别在S1和S2上找出其最接近点对d1=d{p1,p2}和d2=d{q1,q2}，（3）合并：把S1中的点与S2中的点之间的最小距离d’=d{p3,q3}计算出来，最后所求的便是d=min{d1,d2,d}.能否在线性时间内找到p3和q3？能否在线性时间内找到p3和q3如果S的最接近点对是{p3,q3}，即|p3-q3|m}2、d1=cpair2(S1);d2=cpair2(S2);3、dm=min(d1,d2);4、设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐标值排序；并设X和Y是相应的已排好序的点列；5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；6、d=min(dm,dl);returnd;}复杂度分析T(n)=O(nlogn)课堂练习给定一个数组a[1…n]和一个正整数k
本文档为【1007分治法(最近点对)PPT课件】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483