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

Наивный подход часто используется как первое решение, но он плохо масштабируется.

Определение

Наивная реализация скользящего среднего — это алгоритм, который на каждом шаге заново суммирует все элементы текущего окна.

Пример наивного алгоритма

for i in range(n - k + 1):
    window_sum = 0
    for j in range(k):
        window_sum += data[i + j]

Анализ сложности

1. внешний цикл выполняется n раз,

2. внутренний цикл выполняется k раз,

3. общее число операций — n · k.

Частные случаи

• если k — константа, сложность близка к O(n),

• если k ≈ n, сложность становится O(n²).

Практические последствия

• плохо подходит для больших окон,

• быстро становится узким местом по времени.

Вывод

Наивная реализация имеет сложность O(n · k) и подходит только для небольших данных или учебных примеров.