常用算法设计方法5

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

分页:前10页 上一页 11 12 13 14 15 16 17 18 19 [20] 下一页

S₁和

S₂的最接近点对未必就是

S的最接近点对。如果组成

S的最接近点对的

2个点都在

S₁中或都在

S₂中，则问题很容易解决。但是，如果这

2个点分别在

S₁和

S₂中，则对于

S₁中任一点

p，

S₂中最多只有

n/2个点与它构成最接近点对的候选者，仍需做

n²/4次计算和比较才能确定

S的最接近点对。因此，依此思路，合并步骤耗时为

O(n²)。整个算法所需计算时间

T(n)应满足：

T(n)=2T(n/2)+O(n²)

它的解为

T(n)=O(n²)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。

为了使问题易于理解和分析，我们先来考虑一维的情形。此时

分页:前10页 上一页 11 12 13 14 15 16 17 18 19 [20] 下一页

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

发表评论：

匿名发表

用户名:

查看评论

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