알고리즘 - 3 점화식과 점근적 복잡도 분석

재귀 알고리즘과 점화식

1. 점화식의 이해

2. 병합 정렬의 점화식을 이용한 수행시간 분석

 

 

재귀 알고리즘

- 자기 호출을 사용하는 알고리즘

- 명시적으로 자기 호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우 재귀적 성질을 포함하는 알고리즘의 복잡도는 점화식을 이용하여 접근이 가능함

 

점화식

- 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법

- ex.1 등차수열의 점화식 : a_n = a_(n-1) + 2

- ex.2 팩토리얼의 점화식 : n! = n * f(n - 1)

 

 

병합정렬의 점화식을 이용한 수행시간 분석

mergeSort(A[], p, r) // A[p .. r]을 정렬한다.
{
    if (p < r) then{
        q <- (p+r)/2;                     p, r의 중간지점 계산
        mergeSort(A, p, q);                      전반부 정렬
        mergeSort(A, q + q, r);                  후반부 정렬
        merge(A, p, q, r);                            병합
    }
}

merge(A[], p, q, r)
{
   정렬되어 있는 두 배열 A[p ... q]와 A[q+1 ... r]을 합하여
   정렬된 하나의 배열 A[p ... r]을 만든다.
}

 

수행시간의 점화식

- T(n) = 2T(n/2) + 오버헤드

- 크기가 n인 병합정렬 시간

-> 크기가 n/2인 병합 정렬을 2번하고, 나머지 오버헤드를 더한 시간

 

 

점화식의 점근적 분석 방법

1. 점화식의 점근적 분석 방법의 종류

2. 반복 대치

3. 추정 후 증명

4. 마스터 정리

 

 

 

 

점화식의 점근적 분석 방법의 종류

- 점화식으로 표현된 식의 점근적 복잡도를 구하는 방법

- 반복 대치, 추정 후 증명, 마스터 정리

 

 

반복 대치

- 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 방법

T(n) = T(n-1) + n

T(1) = 1
T(n) = T(n-1) + n
     = (T(n-2) + T(n-1)) + n
     ....
     = T(1) + 2 + 3 + ... + n
     = 1 + 2 + ... + n
     = n(n+1)/2
     = 세타(n^2)

 

 

예제 1 - n!를 구하는 문제

factorial(n)
{
     if (n = 1) return 1;
     return n * factorial(n - 1);
}

- T(n) = T(n - 1) + c

- 상수 시간 c : if문을 수행하는 시간과 곱셈을 한번 수행하는 시간

- 크기가 1(즉 , n = 1)인 경우 T(1) <= c이므로 T(n)을 다음과 같이 전개

T(n) = T(n-1) + c = T(n-2) + c + c = T(n - 2) + 2c = T(n - 3) + 3c

      = T(1) + (n - 1) c <= c + (n - 1) c = cn

 

 

추정 후 증명

- 식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옳음을 귀납적으로 증명하는 방법

- T(n) <= 2T(n/2) + n의 점근적 복잡도는 T(n) = O(nlogn)임

 -> 즉, 충분히 큰 n에 대해서 T(n) <= cn log n인 양의 상수 c가 존재함

 

마스터 정리

- 특정한 모양을 가진 재귀식에 대해 바로 결과를 알수있는 정리

- T(n) = a T(n/b) + f(n)

  -> 입력 크기 n인 문제를 풀기 위해 입력 크기 n/b인 문제를 a번 풀고, 나머지 f(n)의 오버헤드가 필요한 알고리즘

- 병합 정렬 :  a = b = 2, f(n) = n인 경우

 

마스터 정리 가정

- a >= 1, b > 1에 대해 T(n) = a T(n/b) + f(n)인 점화식 -> n^(log_b a) = h(n)이라고 가정함