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

Question

Используется подход с накопленной суммой окна. При каждом сдвиге из суммы вычитается элемент, вышедший из окна, и добавляется новый. Среднее затем считается за константное время. Все операции выполняются за O(1) на шаг.

YeaHub · Accepted Answer

Обновление среднего за O(1) — ключевое свойство эффективного скользящего окна.ОпределениеОбновление за O(1) — это выполнение фиксированного числа операций независимо от размера окна.Как это работаетАлгоритм хранит:текущую сумму окна,размер окна k.При каждом сдвиге:window_sum -= outgoing_elementwindow_sum += incoming_elementaverage = window_sum / kПримерwindow_sum += data[right]
window_sum -= data[left]
average = window_sum / k
Почему это эффективнонет вложенных циклов,нет повторных суммирований,минимальное число операций.Где используетсяобработка потоков данных,временные ряды,real-time аналитика.ВыводПодход с накопленной суммой позволяет обновлять среднее при сдвиге окна за O(1) и является стандартным решением для оконных алгоритмов.