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> 예제
'알고리즘 > 알고리즘_학교' 카테고리의 다른 글
6-2강 - Dynamic Programming 2 (최단거리 유형, 플로이드 알고리즘 ) (0) | 2020.11.12 |
---|---|
6-1강 - Dynamic Programming 1 (DP, Binomial Coefficient) (0) | 2020.11.11 |
4-2강 - Euler Cycle(Path) 2 (구현) (0) | 2020.10.09 |
4-1강 - Euler's path(cycle) 1 (개념 정리 및 구현 아이디어) (0) | 2020.10.09 |
3-2강 - 자료구조 & C, C++ programming 2 (Linked List management, Stack & Queue) (0) | 2020.10.03 |