알고리즘 정리 - 점화식과 알고리즘 복잡도 분석

재귀 알고리즘의 복잡도를 구하는 방식은 3가지가 있다.

 

1. 반복대치

2. 추정 후 증명

3. 마스터 정리

 

1. 반복대치

 

반복대치로 복잡도를 구하기 위해서는 먼저 점화식을 구한다.

 

factorial(n)

{

  if(n =1) return 1;

  return n * factorial(n-1);

}

이 식은 다음 점화식으로 나타낼 수 있다.

T(n) = T(n-1) + a (a는 자기호출이외의 수행시간)

그리고 T(1) <= a이다. (T(1)은 자기호출을 하지 않기 때문)

그렇다면 T(n) = T(1) + (n-1)a라고 할 수 있다.

T(n) = a + an - a 이고 T(n) = an이다.

결국 T(n) <= an 이므로. T(n) <= O(n)이라고 증명할 수 있다

 

2. 추정 후 증명

식의 모양을 보고 점근적 복잡도를 추정 후 그것이 옮음을 귀납적으로 증명한다.

 

move(n, a, b, c)

{

  if( 0 < n) {

  move(n-1, a, c, b);

  move(1, a, b, c);

  move(n-1, c, b, a);

  }

}

 

추정 후 증명법을 통해 증명한다.

1. 추정 : T(n) = Ω(2^n) 일 것이다.

 

n이 충분히 클 때, T(n) >= c * 2^n을 만족하는 상수 c가 존재한다.

여기서 계산의 편의성을 위해 c * 2^n + 1로 증명한다.(하한보다 하나 큰 수로 증명하여도 하한이 동시에 증명된다.)

 

move는 T(n) = 2T(n-1) + a 로 나타낼 수 있다.

 

T(n-1) >= c * 2^(n-1) + 1을 만족한다. 따라서 T(n) = 2 * ( c * 2^(n-1) + 1 ) + a 이다.

c * 2^n + a + 2 이고, 이는 c * 2^n + 1보다 크다.

c * 2 ^n + a + 2 >= c * 2^n + 1 이므로,

따라서 T(n) >= Ω(2^n) 가 성립한다.

 

3, 마스터 정리

마스터 정리는 T(n) = aT(n/b) + f(n) 형태의 점화식에 적용할 수 있다.

 

f(n) / h(n)을 구하는데, h(n)은 n^(logb a) 형태이다.

만약 h(n)이 f(n)을 압도한다면, 복잡도는 세타(h(n))이 된다.

만약 f(n)이 h(n)을 압도한다면, 복잡도는 세타(f(n))이 된다.

만약 f(n)과 h(n)이 같다면, 복잡도는 세타(nlogn)이 된다.