1. T(n) = T(4/n) + n^2 (n>1)
c (n=1)
이를 Recursion tree방법을 이용하여 풀어라.
2. S(n) = 0 (n=0)
c + s(n-1) (n>0)
이를 iteration method를 이용하여 풀어라.
[풀이]
S(n) = c + s(n-1)
= c + c + s(n-2)
= 2c + s(n-2)
= 2c + c + s(n-3)
= 3c + s(n-3)
...
= kc + s(n-k) = ck + s(n-k)
'Computer Science > Problem Solving' 카테고리의 다른 글
| [백준 1759 암호 만들기] 문제 해설 (0) | 2019.12.20 |
|---|---|
| 백준 2606번: 바이러스 (0) | 2019.04.27 |
| [작성중][18-알고리즘]배낭 문제(Knapsack Problem) (0) | 2018.06.18 |
| [18-알고리즘]점근적 분석(Asymptotic Analysis)에 대한 예제문제 풀이 (0) | 2018.06.18 |
| [18-알고리즘] 문자열 탐색(String Match) 유한 상태 기계를 통한 문자열 탐색(String matching with finite automata) (0) | 2018.06.17 |