O(N * M) 과 O(N) 으로 해결하는 이동 평균

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

이동평균 (Moving Average)

이동 평균이란 말 그대로 어떤 기간의 평균을 시간의 흐름에 따라 이동하며 구하는 것이다. 예를 들어, 지난 1년 동안 몸무게의 3개월 이동 평균을 구한다면 1~3월의 평균, 2~4월의 평균... 9~11월의 평균, 10~12월의 평균을 구한다.

 

기본적으로 완전 탐색의 방식으로 구할 수 있다. 전체 구간 N 동안 기간 M 에 (N > M) 대한 이동 평균을 구한다면 (N-M+1)*M 만큼 연산하므로 시간 복잡도는 O(N*M).

 

다음은 주어진 몸무게 목록 weight vector 에 대해 interval 만큼의 기간에 대한 이동 평균을 구하는 방법이다.

 

for(int front = 0; front <= weight.size() - interval; ++front){
	partialSum = 0;

	for(int i = front; i < front + interval; ++i) 
    	partialSum += weight[i];

	float average = partialSum / num;
	movingAverage.push_back(average);
}

 

그런데, 이동 평균을 선형 시간에 구하는 방법이 있다. 위 예시를 다시 살펴 보자. 3개월 간의 이동 평균을 구한다면 1~3월, 2~4월 ...  의 데이터를 합산해야 한다. 잘 생각해보면 1~3월의 데이터 합산치에는 2, 3월이 포함돼 있다. 그렇다면 1~3월의 데이터를 구한 뒤 2~4월을 계산할 때는 1월의 데이터를 빼고, 4월의 데이터를 추가하기만 하면 된다.

 

즉, interval 만큼의 반복 연산을 매번 하는 대신,  맨 앞 정보를 버리고 맨 뒤에 정보를 추가하는 상수 시간 연산을 하면 같은 결과를 구할 수 있다.

 

for(int i = 0; i < interval - 1; ++i) partialSum += weight[i];
for(int i = interval - 1; i < weight.size(); ++i){
	partialSum += weight[i];
	movingAverage.push_back(partialSum / interval);
	partialSum -= weight[i - interval + 1];
}

 

이 방법은 전체 구간 N 을 한 번 순회하며 매번 상수 시간의 연산을 수행하므로 O(N) 의 시간 복잡도를 가진다.