이동평균 구하기 - 2

이동평균을 구하는 알고리즘을 서술함 - 2

알고리즘 설명

이동평균 - 1 의 알고리즘은, 매일매일 몸무게를 잰 므두셀라 할아버지의 입장에서 생각하면 이야기가 다름. 므두셀라는 969세까지 살았다고 하니 윤년을 치지 않더라도 969 X 365 = 353,685일을 살았습니다.

미두셀라 옹께서는 나이답게 스케일도 커서, 매일매일 지난 10만 일 (약 274년) 간의 이동평균을 알고 싶어 합니다. 그럼 전체 반복 횟수는 무려 253억 회가 됩니다!

 

어떻게 하면 좀 더 빠른 프로그램을 짤 수 있는지 설명 하겠습니다.

중요한 아이디어는

중복된 계산을 없애는 것

입니다.

므두셀라 옹의 몸무게를 다음과 같이 쭉 늘어놓았다고 가정하겠습니다.

 

날짜	0	1	2	3	...	M - 1	M	M+1
몸무게	3.5	3.5	3.5	3.6	...	80.2	80.1	80.3

측정치가 M개는 되어야 이동 평균을 계산할 수 있으니, 태어난 이후 M-1일부터 이동 평균을 계산할 수 있습니다.

이때, M-1일의 이동 평균과 M일의 이동 평균에 포함되는 숫자들을 표 위에서 찾아 봅시다.

실제 이 둘은 0일과 M일의 몸무게를 제외하면 전부 겹친다는 것을 알 수 있습니다.

그러면 측정한 몸무게의 합을 일일이 구할 것 없이 M-1일에 구했던 몸무게의 합에서 0일째에 측정한 몸무게를 빼고, M일째에 측정한 몸무게를 더하면 어떨까요?

vector<double> movingAverage2(const vector<double>& A, int M){
	vector<double> ret;
	int N = A.size();
	double partialSum = 0;
	for(int i = 0 ; i < M-1; ++i){
		partialSum += A[i];
	}
	for(int i = M-1; i < N; ++i) {
		partialSum += A[i];
		ret.push_back(patialSum / M);
		partialSum -= A[i-M+1];
	}
	return ret;
}

"1" 의 이동평균 구하기와 비교해 두 개의 반복문을 분리했습니다.

따라서 이 반복문의 수행 횟수는

$$M-1+(N-M+1)=N$$

이 됩니다.

수행시간

위 코드의 수행시간은 N에 정비례 합니다. N이 두배 커지면 실행도 두배 오래걸리고, 반으로 줄어들면 수행 시간도 반으로 줄어듭니다. 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 됩니다. 때문에 이런 알고리즘을 선형 시간(Linear Time) 알고리즘 이라고 부릅니다.