Почему пересчёт среднего значения на каждом шаге может быть неэффективным?

Question

Потому что большая часть данных в окне не меняется при его сдвиге. При пересчёте среднего повторно суммируются те же элементы, что приводит к лишним операциям. Это увеличивает время выполнения без реальной пользы.

YeaHub · Accepted Answer

Основная проблема наивного подхода — повторение одинаковых вычислений.ОпределениеИзбыточные вычисления — это повторное выполнение операций над данными, которые не изменились между шагами алгоритма.Что происходит при сдвиге окнаодин элемент выходит из окна,один новый элемент входит в окно,остальные k - 1 элементов остаются прежними.Почему это неэффективноПри полном пересчёте:повторно суммируются неизменившиеся элементы,количество операций растёт линейно с размером окна.Иллюстрация# каждый шаг — пересчёт всей суммы
avg = sum(data[i:i+k]) / k
Практические последствияухудшение масштабируемости,рост времени выполнения при увеличении окна,лишняя нагрузка на CPU.ВыводПересчёт среднего на каждом шаге неэффективен, потому что игнорирует тот факт, что окно меняется минимально. Это и является мотивацией для оптимизированных алгоритмов.