1. 점화식 표현
→ 수열의 어떠한 항을 표현할 때, 그 이전의 항들을 활용하는 것
Ex) 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, ...
→ f(n) = f(n-1) + f(n-2)
→ 위와 같은 표현을 '점화식 표현'이라 한다.
2. Master theorm
3. Fibonacci sequence
→ 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
● 구현
(1) recursive call 방식
#include <stdio.h>
int Fibonacci(int n) {
if (n == 0 || n == 1) //degenerate_case
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
(2) 배열+반복문 활용 방식(재귀X)
#include <stdio.h>
int Fibonacci(int n) {
int Fibo[100];
Fibo[0] = 0;
Fibo[1] = 1;
for (int i = 2; i <= n; i++)
Fibo[i] = Fibo[i - 1] + Fibo[i - 2];
return Fibo[n];
}
● 성능
(1) 재귀함수 | (2) 배열+반복문 | |
점화식 T(n) | T(n-1)+T(n-2)+k | T(n-1) |
Master theorm 계산 | O(2^n) | O(n) |
→ 재귀함수보다 배열과 반복문을 활용하는 것이 더 효율적이다.
(* k: degenerate case)
'알고리즘' 카테고리의 다른 글
[알고리즘] Prologue - Performance & Big-O (0) | 2022.11.05 |
---|