改进O(M N)算法以计算相关性

Question

我有2个数据集，其中包含排序的时间戳

我想计算它们的相关性。

如果2个时间戳匹配，则它们发生在彼此的一定阈值范围内。

我有一个O(m n(算法，我相信它可以正常工作，但是我想知道是否有更好的算法？

本质上，我走两个时间戳的阵列，计算每个时间戳之间的绝对时间差，如果它的时间段短于阈值，则计数器的阈值较短。
我从哪个数组中选择了两个当前时间戳中最早的时间戳，然后重复。
最后，相关性是发现的匹配数除以数据集大小。

这是我到目前为止的伪代码：

matches=0
i=0, j=0
while i < timestamps_1.size and j < timestamps_2.size
    diff = abs(timestamps_1[i] - timestamps_2[j])
    if diff < threshold
        matches += 1
    if timestamps_1[i] < timestamps_2[j]
        i += 1
    else
        j += 1
correlation = matches / timestamps_2.size            

是否有更好的算法可以实现此目标？

Answer 1

在最坏的情况下，没有办法解决这个问题，涉及访问每个数组的每个成员。在最好的情况下，您也许只能访问其中一个阵列的每个成员，另一个成员。订单基于最坏的情况；因此o(n m(