Вопрос проверяет понимание устранения избыточных вычислений и перехода от наивных алгоритмов к оптимальным.
Алгоритм оптимизируют, если перестают пересчитывать сумму окна целиком. Вместо этого поддерживают текущую сумму и обновляют её при сдвиге окна. Такой подход позволяет обрабатывать каждый элемент один раз. В результате временная сложность становится линейной — O(n).
Оптимизация скользящего среднего основана на повторном использовании уже вычисленных значений.
Линейная сложность 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).
подходит для больших потоков данных,
используется в аналитике и мониторинге,
хорошо масштабируется.
Линейная сложность достигается за счёт хранения промежуточного состояния и отказа от полного пересчёта окна.
