Как оптимизировать алгоритм скользящего среднего до линейной сложности?

Question

Алгоритм оптимизируют, если перестают пересчитывать сумму окна целиком. Вместо этого поддерживают текущую сумму и обновляют её при сдвиге окна. Такой подход позволяет обрабатывать каждый элемент один раз. В результате временная сложность становится линейной — O(n).

YeaHub · Accepted Answer

Оптимизация скользящего среднего основана на повторном использовании уже вычисленных значений.ОпределениеЛинейная сложность O(n) означает, что каждый элемент входных данных обрабатывается не более одного раза.Идея оптимизацииПри сдвиге окна:один элемент вычитается из суммы,один элемент добавляется в сумму,среднее считается за константное время.Оптимизированный подходwindow_sum = sum(data[:k])

for i in range(k, len(data)):
    avg = window_sum / k
    window_sum += data[i]
    window_sum -= data[i - k]
Комментарии опущены для краткости: важен сам принцип обновления суммы.Анализ сложностиинициализация окна: O(k),основной цикл: O(n),итоговая сложность: O(n).Практический эффектподходит для больших потоков данных,используется в аналитике и мониторинге,хорошо масштабируется.ВыводЛинейная сложность достигается за счёт хранения промежуточного состояния и отказа от полного пересчёта окна.