常用算法设计方法5

发布时间：2006-07-25 12:02 点击：

分页:前10页 上一页 [21] 22 23 24 25 26 27 28 29 下一页

S中的

n个点退化为

x轴上的

n个实数

x₁、

x₂、…、

x_n。最接近点对即为这

n个实数中相差最小的

2个实数。我们显然可以先将

x₁、

x₂、…、

x_n排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为

O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。

假设我们用

x轴上某个点

m将

S划分为

2个子集

S₁和

S₂，使得

S₁={x∈

S | x≤

m}；

S₂={x∈

分页:前10页 上一页 [21] 22 23 24 25 26 27 28 29 下一页

版权申明:未经书面授权请勿转载本站信息!!作品版权归所属媒体与作者所有!!

发表评论：

匿名发表

用户名:

查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任
留言板管理人员有权保留或删除其管辖留言中的任意内容
本站提醒：不要进行人身攻击。谢谢配合。