文档介绍：最近对问题算法分析与设计最近对问题问题描述:在二维平面上的n个点中,如何快速的找出最近的一对点,就是最近点对问题。程序设计思想::基本思想:分别计算每一对点之间的距离,然后找出距离最小的那一对,为了避免对同一对点计算两次距离,只考虑的那些点对。复杂度分析:对于此算法,主要就是算两个点的欧几里得距离。注意到在求欧几里得距离时,避免了求平方根操作,其原因是:如果被开方的数越小,则它的平方根也越小。所以复杂度就是求平方,求执行次数为:;即时间复杂度为。:基本思想:用分治法解决最近点对问题,就是将一个问题分解两个子问题,然后递归处理子问题,然后合并。可能两个点在每个子问题中,也可能两个点分别在两个子问题中,就这两种情况。则基本过程为:找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素,然后分别求得两边的最短距离,,然后取两者中的最小者记为,在中线两边分别取的距离,记录该距离范围内点的个数,中线左边有个元素,右边有个元素,分别将两边的点按y坐标升序排列,在左边集合中每一个点,找右边集合的点,找到与之距离小于的点,更新最短距离,直到循环结束,即可求出最短距离。复杂度分析:应用分治法求解含有个点的最近对问题,其时间复杂性可由递推式表示:。由以上分析:合并子问题的解的时间。进而可得分治法求最近对问题的时间复杂度为:。程序代码:#include<>#include<>#include<>#defineNUM1000typedefstruct{intx;inty;}N;doubledistance(Nn1,Nn2);doubleminDis(doubled1,doubled2);doubleshortestDis(N*data,intlength,N*n1,N*n2);doubleshortestDis(N*data,intlength,N*n1,N*n2){intpre,last,middle,median;inti,c1num=0,c2num=0,j;N*dataP;N*dataL;N*CP;N*CL;Ntn1,tn2;doubledis1,dis2;//当只有两个点时,返回最短距离,和点if(length==2){doubledis1=distance(data[0],data[1]);*n1=data[0];*n2=data[1];returndis1;}elseif(length==3){//当只有三个点时,返回最短距离,和点doubledis1=distance(data[0],data[1]);doubledis2=distance(data[1],data[2]);doubledis3=distance(data[0],data[2]);doubletemp;temp=dis1<dis2?dis1:dis2;temp=temp<dis3?temp:dis3;if(temp==dis1){*n1=data[0];*n2=data[1];}elseif(temp==dis2){*n1=data[1];*n2=data[2];}else{*n1=data[0];*n2=data[2];}returntemp;}middle=length/2;pre=middle;