본문 바로가기

알고리즘/알고리즘_학교

5-1강 - Divide and Conquer 0 (Solving Recurrences Equations)

0. Solving Recurrences Equations

0) Solving Recurrences by Induction

<example>

이렇게 풀기는 너무 어렵습니다.

그래서 general term 구하는 다른 방법들에 대해 하나씩 알아보겠습니다.

 

1) Using Characteristic Equation - 문제 : Homogeneous Linear Recurrences

1> Theorem 1(서로 다른 근을 가지는 경우)

→ [1] r (r0 ~ r_k-1)에 관한 equation으로 만들고 r들(r0 ~r_k-1)을 구한다.

→ [2] 위 theorem에 따라 t_n을 만든다.

→ [3] t0 ~ t_k-1 초기값 대입

→ [4] k개의 선형 연립 방정식을 통해 c1 ~ ck를 구한다. ( tn의 general term을 구할 수 있다.)

 

2> Theorem 2(중근이 있는 경우)

→ [1] r (r0 ~ rk-1)에 관한 equation으로 만들고 r들(r0 ~rk-1)을 구한다. (중근이 일부 있을 것이다.)

→ [2] 위 theorem 2에 따라 중근인 r은 solution rn, nrn, n2rn 꼴로 만든다. (그리고 theorem 1에 따라 t_n을 만든다.)

→ [3] t0 ~ t_k-1 초기값 대입

→ [4] k개의 선형 연립 방정식을 통해 c1 ~ ck를 구한다. ( tn의 general term을 구할 수 있다.)

2) Using Characteristic Equation - 문제 : Nonhomogeneous Linear Recurrences

solution 구하기 어렵지만 f(n) = bnp(n) 꼴이면 solution 구할 수 있습니다.

 

3> Theorem 3

- b^np(n) + c^nq(n) + .. 처럼 합의 꼴로 되어 있을 수 있다.

[1] 식의 변환을 한다. (a_0~a_k = ..., b= , d= 꼴로 정리하면 좋다.)

 

3) Change of Variable

단순히 변수 변환(치환)을 통해서 우리에게 익숙한 꼴(<non>homogeneous linear recurrence)로 바꾸고

Theorem 1~3을 적용해서 풀어나갈 수 있다.

1> Change of Variable 적용

2> Theorem1~3 중 하나 적용해서 풀이한다. t_n의 일반항을 구할 수 있다.

3> 원래 식에 대입해서 정리한다.

2) Solving Recurrences by Substitution

cf> n=b^k일 때 T(n)=f(n)이면, n이 b^k가 아니어도 T(n)=f(n)이다.

 

3) Master Theorem

0> 용어 정리

- eventually nondecreasing : N이상부터는 nondecreasing이다.

1> Master Theorem

2> 응용

3> 예제