Solving Recurrence Relation

재귀함수를 이용하여 구현된 알고리즘의 경우

시간 복잡도 함수를 구하다 보면 재귀식으로 이루어진 시간 복잡도 함수를 마주하게 된다.

이런 경우 재귀식을 일반식으로 수정해야 하는데, 그 방법을 알아보자.

* 선형인 재귀식의 경우만을 다룹니다.

 

- Homogeneous case

f(n) = 0 인 형태의 식을 homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자.

 

위 식을 생각해보자. tk 항으로 이루어진 재귀식이다.

이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다.

여기서 두 가지 경우로 나뉘는데, (r-1)(r-2)(r-3) 처럼 중근을 갖지 않는 경우와

(r-1)(r-2)^2 처럼 중근을 갖는 경우로 나뉘게 된다.

 

* 중근을 갖지 않는 경우

일반해 tn은 다음과 같이 표현할 수 있다.

* m중근을 갖는 경우

일반해 tn은 다음과 같이 표현할 수 있다.

붉은 색 부분이 중근으로 인해 추가되는 식이다.

1중근, 즉 중근을 갖지 않는 경우 c1r1^n으로 일반 식과 모양이 같아진다.

중근의 경우 c1r1^n + c2nr1^n 같이 n이 한 번 곱해진 항이 추가된다.

3중근의 경우 c1r1^n + c2nr1^n + c3n^2r1^n 같이 n이 1, 2번 곱해진 항이 추가된다.

 

두 경우 모두 ck 라는 상수항이 생기는데, 이는 재귀식의 초깃값을 대입해서 구해주면 된다.

중근이 없는 경우의 예시를 들어보자.

 

중근이 있는 경우의 예시를 들어보자.

 

- Non-homogeneous case

f(n) = 0 인 형태로 표현할 수 없는 식을  non-homogeneous라고 하는데, 이런 경우의 재귀식을 계산하는 법을 알아보자.

 

ai, b는 상수, p(n)은 n에 대한 다항식

위 식을 생각해보자. tk 항으로 이루어진 재귀식이다.

(여기서 c^nq(n) 과 같은 다항식 항이 더 추가될 수도 있다)

이 경우 아래와 같은 특성 방정식(characteristic equation)으로 변환 가능하다.

d는 p(n)의 최고차항의 계수(degree)

(여기서 (r-c)^(e+1) 과 같은 식이 더 추가될 수 있다)

(r-b)^(d+1) 항에서 이미 d+1 중근이 존재한다는 점을 제외하고는 homogeneous case와 같은 모양이다.

그렇기에 이후 일반해를 구하는 과정은 homogeneous case와 동일하다.

 

예시를 들어보자.