Программа для нахождения простой скользящей средней | Сет-2
Простое скользящее среднее — это среднее значение, полученное из данных за некоторый период времени t. В обычном среднем его значение изменяется с изменением данных, но в этом типе среднего значения оно также изменяется с интервалом времени. Мы получаем среднее значение за некоторый период t, а затем удаляем некоторые предыдущие данные. Снова получаем новое среднее значение, и этот процесс продолжается. Вот почему это скользящая средняя. Это имеет большое применение на финансовом рынке. ИЛИ это можно просто визуализировать следующим образом.
Дан arr[] размера N , содержащий только положительные целые числа и целое число K. Задача состоит в том, чтобы вычислить простое скользящее среднее предыдущих K элементов.
Примеры:
Input: { 1, 3, 5, 6, 8 }, K = 3
Output: 0.33 1.33 3.00 4.67 6.33
Explanation: New number added is 1.0, SMA = 0.33
New number added is 3.0, SMA = 1.33
New number added is 5.0, SMA = 3.0
New number added is 6.0, SMA = 4.67
New number added is 8.0, SMA = 6.33Input: Array[]= {2, 5, 7, 3, 11, 9, 13, 12}, K = 2
Output: 1.0 3.5 6 5 7 10 11 12.5
Наивный подход: здесь используются два вложенных цикла. Внешний цикл обходит массив слева направо. Внутренний цикл вычисляет среднее значение K предыдущих элементов, включая самого себя для каждого индекса. Наконец, распечатываются значения скользящего среднего. Внешний цикл начинает обход с самого индекса K. Вместо того, чтобы сохранять результат, мы можем напрямую отобразить вывод, чтобы не использовать лишние пробелы.
Временная сложность: O(N*K)
Сложность пространства: O(1)
Эффективный подход: Эффективный подход обсуждается в Set-1 этой проблемы.
Подход, оптимизированный по пространству: он использует скользящее окно для лучшей эффективности времени и оптимизации пространства. Окно размера K начинается с индекса K, после чего для каждого индекса печатается скользящее среднее.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Сложность пространства: O(1)