[알고리즘] 점화식과 알고리즘 복잡도 분석

1. 점화식

- 점화식은 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것.

- 동일한 함수가 등호나 부등호의 양쪽에 나타나는데, 양쪽 함수는 변수의 크기가 다를 뿐임.

- n!의 점화식은 f(n)=n * f(n-1)

- 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2)

- 점화식은 재귀 함수의 복잡도를 구하는 데 유용함. 자기 호출을 사용하는 알고리즘은 매우 흔함.

- 명시적으로 자기호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우도 있음.

- 재귀적 관계를 이용해 알고리즘의 수행 시간을 점화식으로 표현할 수 있음.

 

mergeSort(A[], p, r) // A[p ~ r]을 정렬함
{
  ① if ( p < r ) then {
        ② q <- (p+r)/2; // p, r의 중간 지점 계산
        ③ mergeSort(A,p,q); // 전반부 정렬
        ④ mergeSort(A,q+1,r); // 후반부 정렬
        ⑤ merge(A,p,q,r); // 병합
    }
}

- 위의 알고리즘은 주어진 문제를 이등분한 다음, 나누어진 문제를 각각 해결하고, 후처리를 함으로써 끝남.

- 크기가 n인 배열의 정렬 문제에 크기 n/2인 배열의 정렬 문제 두 개가 포함됨.

- 그러므로 입력의 크기가 n인 병합 정렬의 수행 시간이 T(n)이면

T(n) = 2T(n/2) + 후처리시간

- T(n)은 크기가 반인 두 개의 문제를 해결하는 시간과 이들을 병합하는 후처리 시간으로 구성됨.

- ①②도 고려할 수 있지만 점근적 수행 시간에 영향을 미치지 않으므로 제외해도 됨.

- 함수 T(n)은 자신보다 크기가 반인 변수로 표현된 함수를 포함하는 점화식

 

2. 점화식의 점근적 분석 방법

반복 대치

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

- n!을 구하는 데 소요되는 시간을 T(n)이라 하면,

T(n) = T(n-1) + c (c는 자기호출을 제외한 나머지의 수행 시간)

- 즉, 입력 n의 계승을 구하는 시간은 입력 n-1의 계승을 구하는 시간에 상수 시간을 더한 것.

- 상수 시간은 ①을 수행하는 시간과 ②의 곱셈을 한 번 수행하는 시간.

- 크기가 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) + c + 2c = T(n-3) + 3c

       ...

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

       ≤ c + (n-1)c

       = cn

∴ T(n) ≤ cn이므로 T(n) = O(n)

 

- 앞 전개처럼 T(n)을 T(n-1)로 대치하고, T(n-1)을 T(n-2)로 대체하고, 계속해서 T(n-2),T(n-3), ... , T(1)까지 반복해서 대치해가는 것과 같은 방식을 사용해 점근적 복잡도를 구함.

 

원래 문제와 이등분된 문제 간의 관계

T(n) ≤ 2T(n/2) + n

 

추정 후 증명

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

- 추정 후 증명법이 유용하게 사용되려면 우선 추정을 의미 있게 해야함.

- 너무 여유롭게 추정하여 증명하는 것은 별로 의미가 없음.

- 무리한 추정은 당연히 증명이 되지 않음.

- 좋은 추정을 하기 위해서는 점화식의 모양에 익숙해져야 함.

- 시각적으로 자기호출 트리를 그려보면서 추정을 하는 경우도 있음.

 

마스터 정리

- 마스터 정리는 특정한 모양을 가진 재귀식에서 바로 결과를 알 수 있는 유용한 정리.

- 마스터 정리가 적용되는 식

T(n) = aT(n/b) f(n)

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