Какой подход позволяет обновлять среднее при сдвиге окна за O(1)?

Обновление среднего за O(1) — ключевое свойство эффективного скользящего окна.

Определение

Обновление за O(1) — это выполнение фиксированного числа операций независимо от размера окна.

Как это работает

Алгоритм хранит:

• текущую сумму окна,

• размер окна k.

При каждом сдвиге:

1. window_sum -= outgoing_element

2. window_sum += incoming_element

3. average = window_sum / k

Пример

window_sum += data[right]
window_sum -= data[left]
average = window_sum / k

Почему это эффективно

• нет вложенных циклов,

• нет повторных суммирований,

• минимальное число операций.

Где используется

• обработка потоков данных,

• временные ряды,

• real-time аналитика.

Вывод

Подход с накопленной суммой позволяет обновлять среднее при сдвиге окна за O(1) и является стандартным решением для оконных алгоритмов.