[Algorithm] 프로그램 수행 시간 짐작하기

참고글 : [Algorithm] 알고리즘 시간 복잡도 분석

#. 프로그램 수행 시간 짐작하기

  ㅇ 시간 복잡도의 분할 상환 분석(amoritzed analysis)

    - 알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것만으로 경정하지 않음

    - 가끔은 문제의 조건에 따라 그보다 더 정확한 시간 복잡도 계산 가능

  ㅇ 수행 시간 짐작하기

    - 프로그램을 작성하기 전 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 함

    - 하지만, 프로그램의 동작 속도에 영향을 끼치는 요소는 엄청나게 많음..

    - 그러나, 많은 경우 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적으로 짐작 가능

  ㅇ 수행 시간 짐작을 위한 주먹구구 법칙

    - "입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다"

    - '이 법칙은 수많은 가정 위에 지어진 사상누각이므로 맹신해서는 안니되오'

      ㄴ 고려해야하는 요소

        - 시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우

        -  반복문의 내부가 복잡한 경우

        - 메모리 사용 패턴이 복잡한 경우

        - 언어와 컴파일러의 차이

        - 구형 컴퓨터를 사용하는 경우

#. 적용

  Q. 1차원 배열 [-7, 4, -3, 6, 3, -8, 3, 4] 에서 연속된 부분 구간 중 그 합이 최대인 구간은?

  A. 최대 합을 갖는 부분 구간은 [4, -3, 6, 3] 으로 합은 10

  ex 1) 주어진 배열의 모든 부분 구간을 순회하면서 그 합을 계산하는 알고리즘 :: 시간 복잡도 O(N^3)

import java.util.*;
 
public class C49 {
    static int MIN = Integer.MIN_VALUE;    // int형 최소값
 
    private static int inefficientMaxSum(final ArrayList<Integer> A){
        int N = A.size();
        int ret = MIN;
        for (int i = 0; i < N; i++) 
            for (int j = i; j < N; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++){
                    sum += A.get(k);
                    ret = Math.max(ret, sum);
                }
            }
        return ret;
    }
    
    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(-7);
        al.add(4);
        al.add(-3);
        al.add(6);
        al.add(3);
        al.add(-8);
        al.add(3);
        al.add(4);
        
        int result = inefficientMaxSum(al);
        System.out.println(result);
    }
}

ex 2) 이동 평균을 빠르게 계산하기 위한 변환 :: 시간 복잡도 O(N^2)

import java.util.ArrayList;
 
public class C49_1 {
    static int MIN = Integer.MIN_VALUE;    // int형 최소값
 
    private static int betterMaxSum(final ArrayList<Integer> A) {
        int N = A.size();
        int ret = MIN;
        for (int i = 0; i < N; ++i) {
            int sum = 0;
            for (int j = i; j < N; ++j) {
                sum += A.get(j);
                ret = Math.max(ret, sum);
            }
        }
        return ret;
    }
    
    public static void main(String[] args) {
        // ...
    }
}
 

ex 3) 분할 정복 기법을 이용한 방법 :: 시간 복잡도 O(NlogN)

import java.util.*;
 
public class C410 {
    static int MIN = Integer.MIN_VALUE;    // int형 최소값
 
    // A[lo ~ hi] 의 연속된 부분 구간의 최대 합
    private static int fastMaxSum(final ArrayList<Integer> A, int lo, int hi) {
        if (lo == hi) return A.get(lo);        // 구간의 길이가 1일 경우
        int mid = (lo + hi) / 2;        // 배열을 두 조각으로 분할
 
        // 분할된 두 부분에 모두 걸쳐 있는 최대 합 구간을 탐색, A[i~mid]와 A[mid+1~j] 형태를 갖는 구간의 합
        int left = MIN, right = MIN;
        // A[i~mid] 형태를 갖는 최대 구간 탐색 
        int sum = 0;
        for (int i = mid; i >= lo; i--) {
            sum += A.get(i);
            left = Math.max(left, sum);
        }
        // A[mid+1~j] 형태를 갖는 최대 구간 탐색 
        sum = 0;
        for (int j = mid + 1; j <= hi; j++) {
            sum += A.get(j);
            right = Math.max(right, sum);
        }
        // 최대 구간이 분할된 두 조각 중 한 구간만 속해 있는 경우
        int single = Math.max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid + 1, hi));
        // 두 경우의 최대치 반환
        return Math.max(left + right, single);
    }
 
    
    public static void main(String[] args) {
        ArrayList<Integer> al = new ArrayList<Integer>();
       // ...
        
        int result = fastMaxSum(al, 0, al.size()-1);
        System.out.println(result);
    }
}

ex 4) 동적 계획법을 사용한 방법 :: 시간 복잡도 O(N)

import java.util.*;
 
public class C411 {
    static int MIN = Integer.MIN_VALUE;    // int형 최소값
 
    private static int fastestMaxSum(final ArrayList<Integer> A)
    {
        int N = A.size();
        int ret = MIN;
        int psum = 0;
        for (int i = 0; i < N; i++)
        {
            psum = Math.max(psum, 0) + A.get(i);
            ret = Math.max(psum, ret);
        }
        return ret;
    }
 
    
    public static void main(String[] args) {
        // ...
    }
}

  ㅇ 수행 시간 짐작

    - O(N^3), O(N^2), O(NlogN), O(N) 의 시간 복잡도를 갖는 알고리즘 수행 시간 짐작

    - 각 테스트 케이스별 시간 제한 1초

    - N의 상한이 1,000, 10,000, 100,000 인 경우

    ㄴ N=1,000 

      - N^3은 10억으로 주먹구구 법칙의 기준을 넘어서므로 O(N^3) 알고리즘을 사용할 때는 주의해야 함

      - 하지만 반복문 내부가 단순하므로 시간 안에 수행 가능할 것으로 짐작, 나머지 세 알고리즘은 별 무리 없이 수행

    ㄴ N=10,000

      - N^3은 1조(기준의 1만 배)이므로 O(N^3) 알고리즘은 시간 안에 돌아갈 가능성이 거의 없음, N^2는 1억 정도이므로 주의해야할 범위에 속함

      - 하지만 반복문 내부가 단순하므로 시간 안에 수행 가능할 것으로 짐작, 나머지 두 알고리즘은 별 무리 없이 수행

    ㄴ N=100,000

      - N^2도 100억(기준의 백 배)이므로 O(N^2) 알고리즘은 시간 안에 들어갈 가능성이 낮음

      - 반면 NlogN은 대략 2천만 정도이므로 남은 두 알고리즘은 별 무리 없이 진행

--

--

--

--

참고 : 알고리즘 문제 해결 전략