计算数组中向量之间的最大距离 [英] Calculate the maximum distance between vectors in an array

问题描述

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

Assume we have an array that holds n vectors. We want to calculate the maximum euclidean distance between those vectors. The easiest (naive?) approach would be to iterate the array and for each vector calculate its distance with the all subsequent vectors and then find the maximum. This algorithm, however, would grow (n-1)! with respect to the size of the array.

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

Is there any other more efficient approach to this problem?

谢谢。

推荐答案

您对朴素算法的复杂度的计算很奇怪，应该为 O（n（ n-1）/ 2），它减小为 O（n ^ 2）。计算两个向量之间的距离为 O（k），其中 k 是向量中元素的数量；这仍然使复杂度大大低于 O（n！）。

Your computation of the naive algorithm's complexity is wonky, it should be O(n(n-1)/2), which reduces to O(n^2). Computing the distance between two vectors is O(k) where k is the number of elements in the vector; this still gives a complexity well below O(n!).

这篇关于计算数组中向量之间的最大距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！