Aсимптотическая сложность взаимной корреляционной функции?

Question

[mimicria]

Интересует верхняя граница O(???) для ВКФ дискретных последовательностей длины l и k (к примеру l меньше k) с единичным лагом

Answer 1

[throughtheether]

Интересует верхняя граница O(???) для ВКФ дискретных последовательностей длины l и k (к примеру l меньше k) с единичным лагом

Навскидку, Ο(k^2). Подразумеваю, последовательности одномерны.
Представим себе окно шириной k, будем в него вдвигать последовательность длины l. Всего возможно k+l вариантов. Для каждого варианта необходимо посчитать скалярное произведение содержимого окна и последовательности длины k (комплексно-сопряженной к исходной), что потребует Θ(k), или Ο(k). Перемножая, отбрасываем младшие члены, получаем Ο(k^2).