이동평균 알고리즘

이동평균 알고리즘 = Moving Average Algorithm

이 알고리즘은 이동하며 변화하는 평균을 구하는 알고리즘이다

값이 자주 변하여 일정기준에 따라 그 값의 평균을 추적하는 알고리즘이라고 생각하면 쉽다

예를들어)

여자친구의 몸무게, 자신의 감정변화, 알코올 섭취량, 주식 등 

시시각각 자주변하는 곳에 적용하여 미래를 예측해보는데 사용된다

어떠한 경우에서 적용이 가능할까?

N개의 측정치, M의 기준 이 주어지면 이동평균을 구할 수 있다

N = 12일

M = 3(일)마다의 이동평균을 구하려고 한다

아~ 최소 3개의 기록이 있어야 구할 수 있겠구나(3일부터~)

12개의 결과가 있는데 3번째 결과부터 그 동안의 3일의 평균을 구하는것이다

이동평균을 구하는 함수를 작성해보았다 (JAVA)

public static ArrayList<Integer> movingAverage(ArrayList<Integer> during, int m) {

ArrayList<Integer> ret = new ArrayList<Integer>();

int size = during.size();

for(int i=m-1; m<size; i++) {

int partialSum = 0;

if(i==15) break;

for(int j=0; j<m; j++) {

partialSum += during.get(i-j);

}

ret.add(partialSum/m);

}

return ret;

}

during = N개의 데이터들이 들어있다 (12개)

m = M(기준)이다. 3을 넘겼다

(코드 이해는 알아서 하기로한다)

하지만 이 코드는 80점짜리라고 생각한다

for를 두번 중첩하였기 때문에 속도면에서 -20점이다

N=12, M=3이라면 실제 반복횟수는 30번이다.

(M * (N-M+1) 에 의해서)

그럼 어떻게해야할까? for 중첩을 안하고는 할 수 없을까...

가능하다!

가만 생각해보면 이동평균의 규칙을 생각해볼 수 있다

1 2 3일의 이동평균 = 1+2+3 / 3 

2 3 4일의 이동평균 = 2+3+4 / 3

3 4 5일의 이동평균 = 3+4+5 / 3

규칙이 보인다

두개씩은 전 이동평균과 겹친다  이 말은 즉

1. 새로운 이동평균을 위해 전의 겹치는 두 개의 값은 그대로 두고 

2. 첫번째를 빼고

3. 현재 일의 값을 더하면 된다

아래는 이 말을 구현한 코드이다(JAVA)

public static ArrayList<Integer> movingAverage(ArrayList<Integer> during, int m) {

ArrayList<Integer> ret = new ArrayList<Integer>();

int size = during.size();

int partialSum = 0;

for(int i=0; i<m-1; i++) {

partialSum += during.get(i);

}

for(int i=m-1; i<size; i++) {

partialSum += during.get(i);

ret.add(partialSum/m);

partialSum -=  during.get(i-m+1);

}

return ret;

}

매개변수는 같다

이렇게 구현하면 실행시간은 size에 정비례하다

size는 무엇인가? during의 길이 -> N이다. (총 데이터 개수)

이렇게 수행시간이 N에 정비례하므로 

N이 두 배 커지면 실행시간도 두 배 커진다

(주어진 값을 최소한 한 번씩 쳐다보기 때문에)

이러한 알고리즘을 선형시간 알고리즘이라고 한다 (linear time)