이동 평균 구하기

이동 평균 구하는 알고리즘을 짯다.

적은 모집단을 가지고 할 때는 반복문을 가지고 하는게 시간 복잡도 측면에서 그렇게 큰 문제가 안되는데 크기가 커지면 문제가 된다.

일단 반복문으로 구하는 알고리즘을 보자.

 

예시로 12개월 치의 몸무게가 주어졌고 매달 3개월간의 이동 평균을 구하는 문제이다.

 

대충 이렇게 돌아간다.

1월과 2월은 3개월치의 자료형이 없으니 빼고, 3월부터 시작한다.

3월에는 1,2,3월의 자료형을 가지고 계산하니 배열의 인덱스로 보면 0,1,2이다. 그래서 i = 2부터 시작하는 이유도 인덱스 2가 3월이기 때문이고, j도 0,1,2가 1,2,3월을 가리킨다.

 

하지만 므두셀라 할아버지는 태어난 날부터 매일매일 몸무게를 쟀습니다. 그는 969세까지 살았다고 합니다. 즉, 353,685일을 살았습니다.

지난 10만일 간의 이동 평균을 구한다고 할 때, 반복 횟수는 253억회가 됩니다. 

 

반복문으로 하기엔 너무 무리가 있다. 좀 더 빠른 알고리즘을 짜는 방법은 뭐가 있을까?

먼저 중복된 계산은 배제해야 한다.

 

날짜        0      1      2      3      4       ...     M-1    M    M+1

몸무게    3.5  3.5   3.5  3.6    3.5    ...     80.2  80.1  80.2

 

M-1일까지의 이동 평균과 M일까지의 이동평균을 비교해보자.

M-1 이동평균은 0일의 3.5를 포함하고 M 이동 평균은 M일의 80.1를 포함한다는 점이다.

그럼 1~M-1일은 무조건 겹친다. 

M 이동 평균을 구할 땐 M-1의 합에서 0을 빼고 M을 더하면 된다.

 

간단하게 0~M-2까지 먼저 더한 후, M-1일의 이동평균을 구하기 위한 M-1을 더해 평균을 구한다. 

 

위와 같이 계산할 경우, 반복문 수행횟수는 처음 for문 M-1번, 두번째 for문 N-M+1번 해서 N번만 수행하면 된다. 253억회에서 353,685회로 줄었다. 결국 N에 비례한다는 의미이다. 이런걸 선형 시간 알고리즘이라 한다.