개요

중첩 반복

M-3 M-2 M-1 M M+1 M+2 … N
0 1 2          
  1 2 3        
    2 3 4      
      3 4 5   N 
/**
  * 이동 평균선 구하기
  * - 이동 평균이란? 시간에 따라 변화하는 값들의 평균
  * - M-이동 평균? 마지막 M개의 평균.
  * */
public double[] first(double[] A, int M) {
    int N = A.length;
    double[] answer = new double[N];

    /* A[i]까지의 이동 평균 구하기 */
    for (int i = M - 1; i < N; i++) {
        double partialSum = 0;
        /* 각 위치(i)에서 지난 M개의 평균 구하기. 현재 기준으로 M-1만큼 돌아간다. */
        for (int j = 0; j < M; j++) { // j는 현재(i)를 기준으로 인덱스를 상대적으로 줄여나가기 위한 변수다
            partialSum += A[i - j]; // 현재(=i)-0, 현재(i)-1, ..., 현재(i)-(M-1)
        }
        answer[i] = partialSum / M;
    }

    return answer;
}

선형 시간 알고리즘

M-3 M-2 M-1 M M+1 M+2 … N
0 1 2          
  1 2 3        
    2 3 4      
      3 4 5   N 
public double[] second(double[] A, int M) {
    int N = A.length;
    double[] answer = new double[N];
    double partialSum = 0;
    /* 미리 중복되는 M-2까지의 합을 구해 둔다 */
    for (int i = 0; i < M - 1; i++) { // M-1 인덱스가 현재(i)며, 현재는 아래 반복문에서 더한다
        partialSum += A[i]; // M=3? A[0], A[1]
    }

    for (int i = M - 1; i < N; i++) {
        partialSum += A[i]; // 현재를 더한다
        answer[i] = partialSum / M;
        partialSum -= A[i - (M - 1)]; // 다음을 위해 현재(i)의 이동 평균선 구하는 첫 시작 부분을 제거한다
    }

    return answer;
}

생각