我有 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
是否有更好的算法来实现这一点？
最佳答案
没有办法解决这个问题，在最坏的情况下，涉及访问每个数组的每个成员。在最好的情况下，您可能只能访问一个数组的每个成员，以及另一个数组的一个成员。订单基于最坏的情况；因此 O(n+m)
关于algorithm - 改进用于计算相关性的 O(m+n) 算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56918163/