[Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 3

안녕하세요, Einere입니다.

(ADBlock을 꺼주시면 감사하겠습니다.)

 

2019/07/02 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1

2019/07/09 - [programing/Algorithm] - [Algorithm] 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2

---

해당 포스트는 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략"을 읽고 간단하게 정리한 포스트입니다.

 

 

 

시간복잡도 분석 방법

• 반복문의 반복 횟수 측정

 

 

 

선형 시간(linear time) 알고리즘

이동평균(moving average)

이동평균은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준입니다.

시간에 따라 관찰된 숫자들이 주어질 때, "M-이동평균"은 마지막 M개의 관찰 값의 평균으로 정의됩니다. 따라서, 새로운 값이 관찰된다면 새 관찰 값을 평균에 포함하도록 바뀝니다.

 

double[] movingAverage(final double[] arr, int m) {
    int n = arr.length;
    double[] ret = new double[n - m + 1];
    
    for(int i = m-1; i < n; i++){
        double partialSum = 0;
        
        for(int j = 0; j < m; j++) {
            partialSum += arr[i-j];
        }
        
        ret[i - (m - 1)] = partialSum / m;
    }
    
    return ret;
}

위 코드는 더블형 배열이 주어졌을 때, m-이동평균을 만들어 반환하는 함수입니다.

위 코드로 arr의 크기와 m이 매우 큰 경우, 엄청난 시너지를 일으켜 엄청난 횟수의 반복을 해야 합니다.

이를 개선하기 위해, 중복계산을 하지 않도록 할 수 있습니다.

 

double[] movingAverage(final double[] arr, int m) {
    int n = arr.length;
    double[] ret = new double[n - m + 1];
    double partialSum = 0;
    
    // 최초의 m-이동평균을 위한 부분합을 구한다.
    for(int i = 0; i < m-1; i++) {
        partialSum += arr[i];
    }
    
    // m-이동평균을 구한다.
    for(int i = m-1; i < n; i++){
        partialSum += arr[i];
        ret[i - (m - 1)] = partialSum / m;
        partialSum -= arr[i - m + 1];
    }
    
    return ret;
}

위와 같이 코드를 변경하면, 시간복잡도는 N에 정비례합니다. 즉, 선형 시간 알고리즘인 것입니다.

 

 

선형 이하 시간(sublinear time) 알고리즘

이진 탐색

이진 탐색은 log2(n)이 걸리므로, 선형 이하 시간 알고리즘입니다.

 

 

지수 시간(exponential time) 알고리즘

대표적으로 멱집합을 구하는 알고리즘은 집합의 원소가 n개인 경우, 반복 횟수가 2^n입니다.

이와 같은 알고리즘은 지수 시간 알고리즘이라고 합니다.

 

다항 시간(polynomial time) 알고리즘

반복 횟수가 입력 크기인 n을 이용한 다항식으로 표현할수 있다면, 다항 시간 알고리즘이라고 합니다. 예를 들어, 반복횟수가 n^2, n^3인 알고리즘도 다항 시간 알고리즘입니다.

 

 

 

 

 

참고

구종만. 프로그래밍 대회에서 배우는 알고리즘 해결전략. 서울:인사이트, 2012.