Об алгоритме (забытом ?) online вычисления корреляции. Опции

[on_river]

Об алгоритме (забытом ?) online вычисления корреляции.
Плохо - когда не знаешь, а еще и забудешь.

1. Рассматривается поток отсчетов сигнала, последовательно поступающий в регистр (вектор) размерности N.
Вычислитель, при поступлении каждого нового отсчета вычисляет вектор значений размерности N
автокорреляционной функции.

2. Известно, вычисление в "лоб" требует выполнения O(n^2) операций, а с привлечением БПФ - O(n*log(n)).

3. Если к пункту 2 кто-либо добавит: "Известен и алгоритм с O(n), вот ссылка ...", буду очень благодарен - вопрос закрыт.


Искренне, с уважением, Владимир.

P.S.

Скажите мне, что я изобрел "колесо" :-).

[_pv]

если на каждый новый отсчёт не пересчитывать целиком через быстрое Фурье, а через обычное, но sliding DFT, то убрать один отсчёт/добавить новый будет пожалуй O(n).

https://www.dsprelated.com/showarticle/776.php