假设我们有一个包含n个向量的数组。我们想要计算这些向量之间的最大欧几里得距离。
最简单(也许有些朴素?)的方法是遍历整个数组,对于每个向量计算它与所有后续向量之间的距离,然后找到最大值。
然而,该算法的时间复杂度会随着数组大小的增加而增长(n-1)!。
还有其他更高效的方法来解决这个问题吗?
谢谢。
还有其他更高效的方法来解决这个问题吗?
谢谢。
O(n(n-1)/2)
,简化后为O(n^2)
。计算两个向量之间的距离是O(k)
,其中k
是向量中的元素数量;这仍然远低于O(n!)
的复杂度。|AB| + |AC| >= |BC|
算法应该是这样的:
如果到目前为止找到的最长距离为MAX
,并且对于一个|AB|
,存在一个点C
,使得距离|AC|
和|CB|
已经计算出来,并且MAX > |AC|+|CB|
,那么我们可以跳过|AB|
的计算。
很难确定这个算法的复杂度,但我的直觉告诉我它不会远离O(N*log(N)*K)