計算數組中向量之間的最大距離

假設我們有一個包含n個向量的數組。我們想要計算這些向量之間的最大歐氏距離。最簡單（樸素？）的方法是迭代數組，併爲每個向量計算其與所有後續向量的距離，然後找到最大值。然而，這個算法會增長（n-1）！關於數組的大小。計算數組中向量之間的最大距離

有沒有其他更有效的方法來解決這個問題？

謝謝。

2012-08-24 kostas

你是什麼意思由向量之間的距離？你如何定義2個向量之間的距離？點清楚，但矢量？ – mathematician1975

兩個向量之間的歐式距離已被很好地定義：sqrt（sum（（x_i-y_i）^ 2））？如果矢量長度不等，你是否擔心？我認爲他的問題意味着所有的載體具有相同的長度。（他在數學意義上使用向量，而不是C++意義） –

可能的重複[如何找到兩個最遠的點？]（http://stackoverflow.com/questions/2736290/how-to-find-two-最遙遠的點） – sdcvvc

您對樸素算法的複雜性的計算結果不可靠，應該是O(n(n-1)/2)，它會減少到O(n^2)。計算兩個向量之間的距離爲O(k)，其中k是向量中元素的數量;這仍然使得複雜度遠低於O(n!)。

2012-08-24 11:13:05

'計算兩個向量之間的距離是O（k^2）' - 這是不正確的。它應該是O（k）。 –

現在使用@ LeonidVolnitsky的更正進行編輯。 –

@HighPerformanceMark歐幾里得空間有一些有用的屬性，它允許你不檢查每一對點。 – Qnan

蠻力算法的複雜性是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)

2012-08-24 13:17:07

不遠處這個問題已經來過這裏，看到How to find two most distant points?

答案是：是可以在歐幾里得空間中以小於O（n^2）完成。又見http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

2012-08-26 11:28:09 Qnan

所以假設你有一對點A和B.考慮超球面分別在北極和南極有A和B.超球體中的任何C點是否比A更遠離A？

進一步假設我們將點集劃分爲每個sqrt（N）點的sqrt（N）超盒。對於任何一對超盒子，我們可以計算出它們中包含的無限點集合中任意兩點之間的最大距離 - 只需計算它們最遠角點之間的距離即可。如果我們已經有一個比這更好的候選人，我們可以放棄這些超級框中的所有點。

2012-08-26 11:50:41

回答