计算数组中向量之间的最大距离

Question

假设我们有一个包含n个向量的数组。我们想要计算这些向量之间的最大欧几里得距离。 最简单（也许有些朴素？）的方法是遍历整个数组，对于每个向量计算它与所有后续向量之间的距离，然后找到最大值。 然而，该算法的时间复杂度会随着数组大小的增加而增长(n-1)!。

还有其他更高效的方法来解决这个问题吗？

谢谢。

- kostas

---

"向量之间的距离"是什么意思？如何定义两个向量之间的距离？对于点来说很清楚，但对于向量呢？ - mathematician1975

两个向量之间的欧几里得距离是明确定义的：sqrt(sum((x_i-y_i)^2))？如果向量长度不相等，你是否担心？我认为他的问题意味着所有向量的长度都相等。（他在使用向量时是指数学意义上的，而不是C++语言中的意义） - Andrew Tomazos

可能是重复的问题：如何找到两个最远的点？ - sdcvvc

@sdcvvc：那个问题是关于2D点集的。而这是一个kD点集。 - Andrew Tomazos

Answer 1

你计算朴素算法复杂度的方法有误，正确应该是O(n(n-1)/2)，简化后为O(n^2)。计算两个向量之间的距离是O(k)，其中k是向量中的元素数量；这仍然远低于O(n!)的复杂度。

- High Performance Mark

---

计算两个向量之间的距离是O(k^2) - 这是不正确的。它应该是O(k)。 - Leonid Volnitsky

欧几里得空间具有一些有用的特性，使您无需检查每对点。 - Qnan

您的第二段似乎暗示着检查每一对可能是我们所能做的最好的事情。但事实并非如此，我们可以做得更好。 - Andrew Tomazos

好的，我已经尝试删除这个答案，但显然一旦它被接受了，我就不能删除它！ - High Performance Mark

哈哈，只需删除第二段。 - Andrew Tomazos

请详细说明O(n!)的情况，因为暴力方法并没有这种复杂度。下面的答案利用了比较欧几里得距离的事实，其中三角不等式适用，可以节省一些计算。 - partizanos

Answer 2

暴力算法的复杂度为O(N^2*K)(K是向量元素数)，但是我们可以通过知道在欧几里得空间中点A、B和C之间的关系来做得更好:

|AB| + |AC| >= |BC|

算法应该是这样的:

如果到目前为止找到的最长距离为MAX，并且对于一个|AB|，存在一个点C，使得距离|AC|和|CB|已经计算出来，并且MAX > |AC|+|CB|，那么我们可以跳过|AB|的计算。

很难确定这个算法的复杂度，但我的直觉告诉我它不会远离O(N*log(N)*K)

- Leonid Volnitsky

Answer 3

这个问题以前就有过，参见如何找到两个最远的点？的解答。

答案是：在欧几里得空间中可以用少于O(n^2)的时间完成。请参考http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/。

- Qnan

Answer 4

假设你有一对点A和B。考虑一个超球体，其中A和B分别位于北极和南极。在超球体中是否存在任何点C距离A比B更远？

进一步假设我们将点集划分为sqrt(N)个每个sqrt(N)个点的超立方体。对于任意一对超立方体，我们可以在k时间内计算出可能包含其中无限点集中任意两点之间的最大距离-只需计算它们最远角之间的距离。如果我们已经有一个比这更好的候选点，我们可以放弃来自那些超立方体的所有点对。

- Andrew Tomazos