Улучшить алгоритм 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)