[C] Fibonacci algorithm , 피보나치수 구하기

피보나치 수열

F(n) = F(n-1) + F(n-2)

 

1. recursive를 이용한 구현

재귀호출을 이용하면 간단하게 구현할 수 있지만, n이 커질수록 연산량이 크게 증가한다. 

시간복잡도 : O(2^n) 

 

2. memoization을 이용한 구현

연산 결과를 저장하는 배열이 필요하지만, 재귀적 구현에 비해 월등히 빠른 속도를 낼 수 있다.

시간복잡도 : O(n) 

3. 간단한 성능 비교

* 15에 대한 피보나치 수를 구하는 실험 진행

recursive 기반 알고리즘은 180,428 cycle이 소요됨

memoization 기반 알고리즘은 6148 cycle이 소요됨

 

memoization 기법이 약 2900% 효율적

* CPU 성능이나 주어진 수에 따라 차이가 있을 수 있습니다.