티스토리 뷰
1. Top-Down 방식: O(2^2/n)
a.k.a : Recursive한 방식.
T(n): fib(n)을 계산하기 위해서 fibonacci함수를 호출하는 횟수
T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2) + 1 (for n >=2)
T(n-1) > T(n-2)임은 명백하고,
T(n-1) + T(n-2) > 2 * T(n-2) 임도 명백하다.
T(n) > ( 2 ^ 1 )T(n-2)이고,
T(n) > ( 2 ^ 2 )T(n-4),
T(n) > ( 2 ^ 3 )T(n-6),
...
T(n) > 2*(n/2)T(0) 일 것이다.
따라서 계산은 2^n/2번 이루어진다.
2. Bottom-Up 방식
1 1 2 3 5 8 13 이런식으로 n(linear)하다. 그러므로 O(n)
'Algorithm > 이론' 카테고리의 다른 글
| [Algorithm] subset sum problem in dynamic programming (0) | 2020.06.17 |
|---|---|
| [Algorithm] 0/1 knapsack problem in dynamic programming (0) | 2020.06.16 |
| [자료구조]다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2019.06.16 |
| [자료구조] 그래프/ DFS(depth-first search) 코드 (0) | 2019.06.10 |
| [자료구조] 그래프 (0) | 2019.06.08 |