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

Question

假设我们有一个包含n个向量的数组。我们要计算这些向量之间的最大欧几里得距离。最简单的方法是对数组进行迭代，然后为每个向量计算其与所有后续向量的距离，然后找到最大值。但是，该算法会增长（n-1）！关于数组的大小。

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

谢谢。

Answer 1

您对朴素算法的复杂性的计算是靠不住的，它应该是O(n(n-1)/2)，这会减少到O(n^2)。计算两个向量之间的距离，O(k)其中k是向量中元素的数量；这仍然给出了远低于 的复杂性O(n!)。