점화식 (Recurrence Relations)

Recurrence Relations, 점화식, 재귀 관계, 마스터 정리, 생성함수 풀이, 특성 방정식

정의

점화식 (Recurrence Relation) 은 수열 $(a_n)$ 의 $n$ 번째 항을 앞선 항 (또는 몇 개) 로 표현하는 관계식입니다.

초기 조건 과 점화식이 함께 있으면 수열의 모든 항을 순차적으로 결정 가능.

예: 피보나치 $F_n=F_{\{}n-1\}+F_{\{}n-2\}$, $F_0=0,F_1=1$.

컴퓨터 과학 응용: 재귀 알고리즘의 시간 복잡도, 자료구조의 크기 분석, 동적 계획법의 상태 전이.

유명한 점화식

1. 피보나치 수열

$F_n=F_{\{}n-1\}+F_{\{}n-2\},F_0=0,F_1=1$

값: $0,1,1,2,3,5,8,13,21,34,\dots$

2. 팩토리얼

$n!=n\cdot (n-1)!,0!=1$

3. 하노이 탑

$n$ 판을 옮기는 최소 이동 수:

$T_n=2T_{\{}n-1\}+1,T_1=1$

풀이: $T_n=2^n-1$.

4. 병합 정렬 시간 복잡도

$T(n)=2T(n/2)+O(n)$

풀이 (마스터 정리): $T(n)=O(n\log n)$.

5. 이항 계수

$\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}=(\genfrac{}{}{0ex}{}{\{}{n})-1\}\{k-1\}+\left(\genfrac{}{}{0ex}{}{\{}{n}\right)-1\}\{k\}$

6. 카탈란 수

$C_n={\sum }_{\{}i=0{\}}^{\{}n-1\}{C}_i{C}_{\{}n-1-i\},C_0=1$

값: $1,1,2,5,14,42,\dots$

시각화: 재귀 트리

예: $T(n)=2T(n/2)+n$ 의 재귀 트리.

                    n
                   /  \
                 n/2   n/2       (합 = n)
                / \   / \
              n/4 n/4 n/4 n/4    (합 = n)
              ...
             ...
             1 1 1 ... 1          (n 개의 잎)

레벨 수 = ${\log }_{2}n$. 각 레벨의 합 = $n$. 총 = $n\log n$.

선형 점화식 풀이

형태

$a_n=c_1{a}_{\{}n-1\}+c_2{a}_{\{}n-2\}+\dots +c_k{a}_{\{}n-k\}$

$c_i$ 는 상수, $c_k\ne 0$. $k$ 차 선형 동차 상수 계수 점화식.

특성 방정식

$a_n=r^n$ 이라고 가정. 대입:

$r^k=c_1{r}^{\{}k-1\}+c_2{r}^{\{}k-2\}+\dots +c_k$

$r^k-c_1{r}^{\{}k-1\}-\dots -c_k=0$

이 방정식의 해 $r_1,r_2,\dots ,r_k$ 가 특성근.

일반해 (서로 다른 특성근)

$a_n=A_1{r}_1^n+A_2{r}_2^n+\dots +A_k{r}_k^n$

$A_i$ 는 초기 조건으로 결정.

예: 피보나치

$F_n=F_{\{}n-1\}+F_{\{}n-2\}$.

특성 방정식: $r^2-r-1=0$

$r=\frac{\{}{1}\pm \sqrt{5}\}2$

$\varphi =\frac{\{}{1}+\sqrt{5}\}2$ (황금비), $\psi =\frac{\{}{1}-\sqrt{5}\}2$.

$F_n=A{\varphi }^n+B{\psi }^n$

초기 조건 $F_0=0,F_1=1$ 대입:

$F_n=\frac{1}{\{}\sqrt{5}\}\left({\varphi }^n-{\psi }^n\right)$

(Binet의 공식)

중복근

특성근 $r$ 이 $m$ 중근이면 항: $(A_0+A_{1}n+\dots +A_{\{}m-1\}{n}^{\{}m-1\})r^n$

예: $a_n=4a_{\{}n-1\}-4a_{\{}n-2\}$.

특성 방정식: $r^2-4r+4=(r-2{)}^2=0$. $r=2$ (중근).

일반해: $a_n=(A+Bn)2^n$.

비동차 (비선형 항 있음)

$a_n=c_1{a}_{\{}n-1\}+\dots +c_k{a}_{\{}n-k\}+f(n)$

$f(n)\ne 0$ 이면 비동차.

일반해 = 동차해 + 특수해

특수해 형태는 $f(n)$ 형태에 따라 시행. $f(n)=P(n)s^n$ (다항식 × 지수) 이면 특수해도 유사 형태.

예: $a_n=2a_{\{}n-1\}+3^n$

동차해: $r=2\Rightarrow A\cdot 2^n$

특수해 시도: $a_n^{\{}(p)\}=c\cdot 3^n$. 대입:

$c\cdot 3^n=2c\cdot 3^{\{}n-1\}+3^n$

$3c=2c+3$

$c=3$

일반해: $a_n=A\cdot 2^n+3\cdot 3^n=A\cdot 2^n+3^{\{}n+1\}$

마스터 정리 (Master Theorem)

분할 정복 재귀:

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

• $a\ge 1$: 하위 문제 수
• $b>1$: 크기 축소 비율
• $f(n)$: 분할/병합 비용

세 경우:

1. $f(n)=O(n^{\{}{\log }_{b}a-ϵ\})$ ($ϵ>0$): $T(n)=\Theta (n^{\{}{\log }_{b}a\})$
2. $f(n)=\Theta (n^{\{}{\log }_{b}a\})$: $T(n)=\Theta (n^{\{}{\log }_{b}a\}\log n)$
3. $f(n)=\Omega (n^{\{}{\log }_{b}a+ϵ\})$ 이고 정규 조건: $T(n)=\Theta (f(n))$

알고리즘 예

알고리즘	점화식	결과
이진 탐색	$T(n)=T(n/2)+1$	$\Theta (\log n)$
병합 정렬	$T(n)=2T(n/2)+n$	$\Theta (n\log n)$
카라추바 곱셈	$T(n)=3T(n/2)+n$	$\Theta (n^{\{}{\log }_{2}3\})\approx \Theta (n^{1.585})$
Strassen 행렬 곱	$T(n)=7T(n/2)+n^2$	$\Theta (n^{\{}{\log }_{2}7\})\approx \Theta (n^{2.807})$

생성함수 (Generating Functions)

수열을 함수로.

$G(x)={\sum }_{\{}n=0{\}}^{\{}\infty \}{a}_n{x}^n$

예: 피보나치

$G(x)=\sum F_n{x}^n$. 점화식 $F_n=F_{\{}n-1\}+F_{\{}n-2\}$ 로:

$G(x)-xG(x)-x^{2}G(x)=F_0+(F_1-F_0)x=x$

$G(x)=\frac{\{}{x}\}\{1-x-x^2\}$

부분 분수 분해 -> $F_n$ 의 닫힌 공식.

유용성

• 조합 항등식 증명
• 확률 생성 함수
• 재귀 관계 해결
• 점근 분석

자세한 것은 생성함수 참조.

유용한 점화식 표

점화식	해
$a_n=a_{\{}n-1\}+c$	$a_n=a_0+cn$
$a_n=c\cdot a_{\{}n-1\}$	$a_n=a_0{c}^n$
$a_n=a_{\{}n-1\}+f(n)$	$a_n=a_0+{\sum }_{\{}k=1{\}}^{\{}n\}f(k)$
$a_n=c{a}_{\{}n-1\}+f(n)$	$a_n=c^n{a}_0+{\sum }_{\{}k=1{\}}^{\{}n\}{c}^{\{}n-k\}f(k)$
$T(n)=2T(n/2)+n$	$\Theta (n\log n)$
$T(n)=T(n-1)+O(1)$	$\Theta (n)$
$T(n)=T(n-1)+n$	$\Theta (n^2)$
$T(n)=2T(n-1)+1$	$\Theta (2^n)$

컴퓨터 과학 응용

알고리즘 분석

재귀 알고리즘의 시간 복잡도 = 점화식.

• 이진 탐색: $T(n)=T(n/2)+O(1)$
• 병합 정렬: $T(n)=2T(n/2)+O(n)$
• 퀵 정렬 (worst): $T(n)=T(n-1)+O(n)$

동적 계획법

DP 는 근본적으로 점화식.

• 피보나치 $F_n=F_{\{}n-1\}+F_{\{}n-2\}$
• LCS: $L[i][j]=\max (L[i-1][j],L[i][j-1],L[i-1][j-1]+1[a_i=b_j])$
• 배낭: $K[i][w]=\max (K[i-1][w],K[i-1][w-w_i]+v_i)$

자료구조

• B-tree 높이: $h=O({\log }_{M}n)$ ($M$ = 분기)
• 힙 삽입/삭제: $O(\log n)$
• AVL 트리: 회전 균형

확률

• 랜덤 워크의 재귀: $E[T_n]=c+\frac{1}{2}(E[T_{\{}n-1\}]+E[T_{\{}n+1\}])$
• 랜덤 알고리즘의 기댓값 분석

함정

1. 초기 조건 개수

$k$ 차 점화식은 $k$ 개의 초기 조건 필요. $F_n=F_{\{}n-1\}+F_{\{}n-2\}$ 는 $F_0,F_1$ 필요.

2. 특성 방정식 근

중복근 처리 잊지 말 것. $(r-r_0{)}^m$ 이면 $n^0,n^1,\dots ,n^{\{}m-1\}$ 곱한 항.

3. 마스터 정리 경우 3

정규 조건 (regularity): $af(n/b)\le cf(n)$ ($c\text{<}1$). 대부분 성립하지만 확인 필요.

4. 지수 vs 다항

$T(n)=2T(n/2)+1$ 는 $\Theta (n)$ (지수 ${\log }_{2}2=1$). $T(n)=2T(n-1)+1$ 는 $\Theta (2^n)$ (분할 대신 감소).

두 형태 구분 필수.

관련 위키

• 이산수학 (개요)
• 증명 기법 - 귀납법
• 조합론
• 생성함수
• 카탈란 수
• 그래프 이론
• DP 최적화 - 관련 알고리즘