分治法和蛮力法求最近对问题_最近对问题分治代码 - CSDN文库

最近对问题

5星 · 超过95%的资源需积分: 50 41 浏览量更新于2023-03-16 评论 12 收藏 109KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

《算法设计与分析》实验报告

学号：姓名：

日期：得分：

一、实验内容：

分治法和蛮力法求最近对问题及其时间复杂度比较。

二、所用算法的基本思想及复杂度分析：

1.蛮力法求最近对问题：

1）基本思想：

分别计算每一对点之间的距离，然后找出距离最小的那

一对，为了避免对同一对点计算两次距离，只考虑的那些点

对。

2）复杂度分析：

对于此算法，主要就是算两个点的欧几里得距离。注意到在求

欧几里得距离时，避免了求平方根操作，其原因是：如果被开方的

数越小，则它的平方根也越小。所以复杂度就是求平方，求执行次

数为：

; 即时间复杂度

为。

2.分治法求最近对问题：

1）基本思想：

用分治法解决最近点对问题，就是将一个问题分解两个子

问题，然后递归处理子问题，然后合并。可能两个点在每个子问题

中，也可能两个点分别在两个子问题中，就这两种情况。则基本过

程为：找一条中垂线(坐位集合坐标的中位数)把个元素分成左右两

部分元素，然后分别求得两边的最短距离,，然后取两者中的最小者

记为，在中线两边分别取的距离，记录该距离范围内点的个数，中

线左边有个元素，右边有个元素，分别将两边的点按 y 坐标升序排

列，在左边集合中每一个点，找右边集合的点，找到与之距离小于

的点，更新最短距离，直到循环结束，即可求出最短距离。

2）复杂度分析：

应用分治法求

解含有个点的最近对问题，其时间复杂性可由递推式表示：。

由以上分析：合并

子问题的解的时间。

进而可得分治法求最近对问题的时间复杂度为：。

三、源程序及注释：

#include<iostream>

1

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

评论6

wudewang2012

2014-05-13

挺好的，对我帮助挺大的，谢谢

XACKWXl

粉丝: 3
资源: 10

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈