精选优质文档-倾情为你奉上算法设计与分析实验报告学 号： 姓 名： 日 期： 得 分： 1、 实验内容：分治法和蛮力法求最近对问题及其时间复杂度比较。二、所用算法的基本思想及复杂度分析：1.蛮力法求最近对问题：1） 基本思想：分别计算每一对点之间的距离，然后找出距离最小的那一对，为了避免对同一对点计算两次距离，只考虑的那些点对。2）复杂度分析：对于此算法，主要就是算两个点的欧几里得距离。注意到在求欧几里得距离时，避免了求平方根操作，其原因是：如果被开方的数越小，则它的平方根也越小。所以复杂度就是求平方，求执行次数为：;即时间复杂度为。2.分治法求最近对问题：1）基本思想：用分治法解决最近点对问题，就是将一个问题分解两个子问题，然后递归处理子问题，然后合并。可能两个点在每个子问题中，也可能两个点分别在两个子问题中，就这两种情况。则基本过程为：找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两部分元素，然后分别求得两边的最短距离,，然后取两者中的最小者记为
