《算法设计与分析》实验报告 姓 名： 得 分： 学 号： 日 期： 一、实验内容： 分治法和蛮力法求最近对问题及其时间复杂度比较。 二、所用算法的基本思想及复杂度分析： 1.蛮力法求最近对问题： 1）基本思想： 分别计算每一对点之间的距离，然后找出距离最小的那一对，为了 避免对同一对点计算两次距离，只考虑 j i  的那些点对 i PP, 。 j 2）复杂度分析： 对于此算法，主要就是算两个点的欧几里得距离。注意到在求欧 几里得距离时，避免了求平方根操作，其原因是：如果被开方的数越 小，则它的平方根也越小。所以复杂度就是求平方，求执行次数为： )( nT  ( nn )1  2nO ( ) ;即时间复杂度为 ( 2nO 。 ) 2.分治法求最近对问题： 1）基本思想： 用分治法解决最近点对问题，就是将一个问题分解两个子问题， 然后递归处理子问题，然后合并。可能两个点在每个子问题中，也可 能两个点分别在两个子问题中，就这两种情况。则基本过程为：找一 条中垂线 m (坐位 S 集合 x 坐标的中位数)把 n 个元素分成左右两部 分元素，然后分别求得两边的最短距离 1d , 2d ，然后取两者中的最 小者记为 d ，在中线两边分别取 d 的距离，记录该距离范围内点的个 数，中线左边有 L 个元素，右边有 R 个元素，分别将两边的点按 y 坐 标升序排列，在左边集合中每一个点，找右边集合的点，找到与之距 离小于 d 的点，更新最短距离，直到循环结束，即可求出最短距离。 2）复杂度分析： 应用分治法求解含有 n 个点的最近对问题，其时间复杂性可由递推式 表示： )( nT  (*2 nT )2/  )( nf 。 由以上分析：合并子问题的解的时间 )( Onf  )1( 。进而可得分治法 ( nOnT )(  log 2 n ) 。 求最近对问题的时间复杂度为： 三、源程序及注释： #include 1 

#include #include #include #include using namespace std; #define eps 1e-8 #define MAXN 10000000 #define N 5000 struct Point { double x,y; }; Point S[N*2],S1[N],S2[N],P1[N],P2[N]; double Distance(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int cmp1(Point a, Point b) { return a.xb?b:a; } //分治法求最近对问题 double ClosestPoints1(Point S[],int n) { int i,j,m; if (n<2) return MAXN; else { double d0=MAXN; double d,d1,d2; int k1=0; int k2=0; int j1=0; int j2=0; sort(S,S+n,cmp1); Point p=S[n/2]; 2 

//m=S 中各点 x 坐标的中位数 m=p.x; for(i=0;i<(n+1)/2;i++) { S1[j1].x=S[i].x; S1[j1].y=S[i].y; j1++; //构造 S1 中点的坐标小于 m } for(i=(n+1)/2;i

double ClosestPoints2(Point S[],int n) { double d0=MAXN; for(int i=0;i

比较运行结果，得出结论，分治法与蛮力法所求结果相同，从运行时间上来 讲分治法运行远远快于蛮力法。 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 1.课本只给出了伪代码，具体的实验要靠自己动手上机反复实验才能完成。 要通过赋简单值法来初步检验程序的是否正确，再以相同数据检验两种方法的运 行结果是否一致来进一步判断程序是否正确，同时使得两种算法的比较更加公 平，实验更有可信度。 2.要比较分治法和蛮力法求最近对问题的时间复杂度，就要两者各自的运行 时间。为此，必须要有大量数据，便利用了 rand（）函数产生大量随机数，还 增加了实验可信度。 3.不要太迷信课本。其中课本上伪代码的函数返回值类型定义为 int 型，使 得赋简单值时运行结果始终为 0，注意到这一点，将 int 改为 double 才得到了 较准确的运行结果。所以，编程是要自己多动脑思考，才能真正解决问题。 5