알고리즘의 시간 복잡도 분석 - 2.선형 시간 알고리즘

이동 평균 (moving average)

주식 가격, 연간 국내 총생산(GDP), 몸무게 등 시간에 따라 변화하는 값을 관찰할 때 유용하게 사용할 수 있는 통계적 기준

 

M-이동 평균

마지막 M개의 관찰 값의 평균

(새 관찰 값이 나오면 그 값을 포함하도록 바뀜)

 

 

N개의 측정치가 주어질 때 매달 M달 간의 이동 평균을 계산하는 것 을 코드로 작성해보자.

 

// 길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double>& A, int M){
	vector<double> ret;
    int N = A.size();
    for(int i = M-1; i < N; ++i){
    	//A[i]까지의 이동 평균 값을 구하자.
        double partialSum = 0;
        for(int j = 0; j < M; ++j)
        	prtialSum += A[i-j];
        ret.push_back(partialSum / M);
    }
    return ret;
}

수행 시간

j를 사용하는 반복문은 (M) 번 실행되고, i를 사용하는 반복문은 (N - M + 1) 번 실행되므로, 전체 반복문은 M * (N - M + 1) 이 된다.

 

N이 작은 수라고 한다면 이 알고리즘은 수행 시간이 빠르다. 하지만 큰 수를 생각해보자.

 

EX)

태어난 날부터 매일매일 몸무게를 잰 사람이 현재 969세라고 하자.

그렇다면 총 N은 969 * 365 = 353,685 가 될 것이다.

매일매일 지난 10만 일 간의 이동 평균을 구하고자 할 때, 전체 반복 횟수는 무려 253억 회가 된다!

 

좀 더 빠른 프로그램을 만들 수는 없을까?

=> 중복된 계산을 피하자.

 

// 길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 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(partialSum / M)
        partialSum -= A[i-M+1];
    }
    return ret;
}

알고리즘

- (0) 번째부터 (M-1) 번째까지의 값의 합을 계산한다.

- M번째 값을 더하고 이동 평균을 계산한다. 그 후 0 번째 값을 뺀다.

- 이것을 i 값을 증가시켜가며 모든 이동 평균을 계산한다.

 

수행 시간

2개의 반복문이 있으므로, (M - 1) + (N - M + 1) = N 이 된다.

 

수행 시간은 N에 정비례한다. 입력에 대비해 걸리는 시간을 그래프로 그리면 정확이 직선이 된다.

이를 선형 시간 알고리즘이라고 한다.