相关疑难解决方法(0)

这是我前一段时间在求职面试时被问到的问题.而我仍然无法找出合理的答案.

问题是:

你得到一组点(x,y).找到2个最遥远的点.相互遥远.

例如,对于点:(0,0),(1,1),( - 8,5) - 最远的是:(1,1)和(-8,5)因为它们之间的距离较大(0,0) - (1,1)和(0,0) - ( - 8,5).

显而易见的方法是计算所有点之间的所有距离,并找到最大值.问题是它是O(n ^ 2),这使得它对于大型数据集而言过于昂贵.

有一种方法是在边界上有第一个跟踪点,然后计算它们的距离,前提是边界上的点数少于"内部",但它仍然很昂贵,并且在最坏的情况下会失败.

试图搜索网络,但没有找到任何明智的答案 - 虽然这可能只是我缺乏搜索技巧.

我有一个MxN数组,其中M是观察数量,N是每个向量的维数.从该阵列矢量的,我需要计算mean和minimum欧几里得距离向量之间.

在我看来,这需要我计算_M C ₂距离,这是一个O(n ^min(k,nk))算法.我M的约为10,000,我N的约为1,000,这个计算需要约45秒.

是否有更有效的方法来计算mean和min距离？也许是一种概率方法？我不需要它准确,只需要关闭.