假设我们有保持n个向量的阵列。 我们要计算这些矢量之间的最大欧氏距离。 最简单的（幼稚？）的方法是迭代的阵列和用于每个矢量计算其距离与所有后续的矢量，然后找到最大。 这种算法，但是，会增加（N-1）！ 相对于所述阵列的大小。
是否有其他更有效的方法解决这个问题？
谢谢。
Answer 1:
您的朴素算法的复杂性的计算是靠不住的，它应该是O(n(n-1)/2)这减少了O(n^2) 计算两个向量之间的距离为O(k)其中k是在矢量元素的数量; 这仍然给出了一个复杂度远低于O(n!)
Answer 2:
复杂度为O（N ^ 2 * K）为蛮力算法（K是矢量ELEM数）。 但是，我们可以通过做明知欧氏空间中的点A，B和C更好：
|AB| + |AC| >= |BC|
算法应该是这样的：
如果迄今发现的最大距离为MAX并为|AB| 有一个点C ，使得距离|AC| 和|CB| 已经计算和MAX > |AC|+|CB| ，那么我们就可以跳过计算|AB| 。
这是很难说这种算法的复杂性，但我的直觉告诉我，这是不远处O(N*log(N)*K)
Answer 3:
这个问题一直在这里之前，请参阅如何找到两个最远点？
答案是：是可以在不到欧氏空间中为O（n ^ 2）来完成。 又见http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/
Answer 4:
因此，假设你有一双点A和B.考虑分别在南北极有A和B超球。 可以包含在超球面的任何点C从A不同于B更远？
进一步假设我们划分点集成的sqrt（N）与SQRT双曲盒（N）的每个点。 通过简单地计算它们的最远的角部之间的距离 - 对于任何一对双曲盒的，我们可以在K个时计算最大距离的无限集合包含在其中点中的任意两点之间的可能。 如果我们已经有了一个候选人比这更好的，我们可以放弃所有对那些双曲点。
文章来源: Calculate the maximum distance between vectors in an array
