假设我们有一个包含 n 个向量的数组。我们想计算这些向量之间的最大欧几里得距离。最简单的（天真的？）方法是迭代数组并为每个向量计算其与所有后续向量的距离，然后找到最大值。然而，这个算法会增长（n-1）！关于数组的大小。
有没有其他更有效的方法来解决这个问题？
谢谢。
问问题
4132 次
4 回答
4
您对朴素算法复杂性的计算很不稳定，它应该是O(n(n-1)/2)，它减少到O(n^2)。计算两个向量之间的距离是向量O(k)中k元素的数量；这仍然给出了远低于O(n!).
于 2012-08-24T11:13:05.320 回答
3
蛮力算法的复杂度为 O(N^2 * K)（K 是向量中元素的数量）。但是我们可以通过知道在欧几里得空间中的点 A、B 和 C 来做得更好：
|AB| + |AC| >= |BC|
算法应该是这样的：
如果到目前为止找到的最大距离是MAX并且对于 a|AB| 有一个点C，例如距离|AC|和|CB|已经计算和MAX > |AC|+|CB|，那么我们可以跳过计算|AB|。
很难说出这个算法的复杂性，但我的直觉告诉我它离我不远O(N*log(N)*K)
于 2012-08-24T13:17:07.043 回答
2
这个问题之前一直在这里，请参阅如何找到两个最远的点？
答案是：在欧几里得空间中可以在小于 O(n^2) 的时间内完成。另见http://mukeshiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/
于 2012-08-26T11:28:09.523 回答
0
因此，假设您有一对点 A 和 B。考虑分别在北极和南极具有 A 和 B 的超球面。超球面中包含的任何点 C 是否可以比 B 更远离 A？
进一步假设我们将点集划分为 sqrt(N) 个超框，每个超框有 sqrt(N) 个点。对于任何一对超框，我们可以在 k 时间内计算它们中包含的无限点集合中任意两点之间可能的最大距离——通过简单地计算它们最远角之间的距离。如果我们已经有一个比这更好的候选者，我们可以丢弃这些超框中的所有点对。
于 2012-08-26T11:50:41.280 回答