Java:距离度量算法设计

Question

我正在尝试用Java解决以下问题(尽管它可以用几乎任何其他语言来完成)：

我得到了两个整数值数组，xs和ys，它们表示x轴上的dataPoints。它们的长度可能不相同，尽管它们都大于0，并且不需要对它们进行排序。我想要计算的是两个数据点之间的最小距离度量。我的意思是，对于每个x，我在ys集合中找到最接近的y，并计算距离，例如(x-y)^2。例如：

xs = [1,5]
ys = [10,4,2]

应返回(1-2)^2 + (5-4)^2 + (5-10)^2

距离测量并不重要，它是我感兴趣的算法。我在考虑对这两个数组中的数组进行排序，并在这两个数组中提前索引，以实现比bruteforce更好的结果(对于x中的每个元素，扫描ys中的所有元素以找到min)，即O(len1 * len2)。

这是我自己的问题，不是家庭作业问题。您的所有提示都将不胜感激。

Answer 1

我假设HighPerformanceMark (对你的问题的第一个评论)是对的，你实际上选择了较大的数组，为每个元素找到最接近的较小数组中的一个，并在这些距离上求和一些f(dist)。

我会推荐你的方法：

Sort both arrays 
indexSmall=0 

// sum up
for all elements e in bigArray {
  // increase index as long as we get "closer"
  while (dist(e,smallArray(indexSmall)) > dist(e,smallArray(indexSmall+1)) {
    indexSmall++
  }
  sum += f(dist(e,smallArray(indexSmall)));
}

它是用于排序的O(max(len1,len2)*log(max(len1,len2)))。其余部分与较大的数组长度呈线性关系。现在，dist(x,y)应该是类似于abs(x-y)、f(d)=d^2或任何你想要的东西。

Answer 2

你提出的想法听起来不错。您可以在O(n logn)时间内对列表进行排序。然后，您可以对较长的列表进行单次迭代，使用另一个列表上的滑动索引来查找“对”。随着你在更长的列表中前进，你将永远不会在另一个列表上走回头路。所以现在你的整个算法是O(n logn + n) = O(n logn)。

Answer 3

您的方法非常好，并且具有O(n1*log(n1)+n2*log(n2))时间复杂度。

如果数组的长度不同，另一种方法是：

1. 从开始到结束对较短的数组进行排序，使用二进制搜索在排序的较短数组中查找最近的项。

这具有O((n1+n2)*log(n1))时间复杂度，其中n1是较短数组的长度。