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

Question

Наивная реализация пересчитывает среднее заново для каждого окна. Если размер окна равен k, а длина данных — n, то для каждого из n шагов выполняется k операций. Итоговая сложность такого алгоритма — O(n · k).

YeaHub · Accepted Answer

Наивный подход часто используется как первое решение, но он плохо масштабируется.ОпределениеНаивная реализация скользящего среднего — это алгоритм, который на каждом шаге заново суммирует все элементы текущего окна.Пример наивного алгоритмаfor i in range(n - k + 1):
    window_sum = 0
    for j in range(k):
        window_sum += data[i + j]
Анализ сложностивнешний цикл выполняется n раз,внутренний цикл выполняется k раз,общее число операций — n · k.Частные случаиесли k — константа, сложность близка к O(n),если k ≈ n, сложность становится O(n²).Практические последствияплохо подходит для больших окон,быстро становится узким местом по времени.ВыводНаивная реализация имеет сложность O(n · k) и подходит только для небольших данных или учебных примеров.