피보나치 수

피보나치 수는 0 1 1 2 3 5 8 13 21... 순으로 앞의 두 수를 더한 값이 지금의 수가 되는 수열이다. 

 

fib(n)=0                     (n=0)

fib(n)=1                     (n=1)

fib(n)=fib(n-1)+fib(n-2)  (n>=2)

 

n일 때 fib(n)을 구한다면 T(n)의 시간이 걸린다. T(n)이 구해지는 시간을 구하는 것은 fib(n-1)을 구하는 것과 fib(n-2)를 구하는 것의 시간을 합친것과 같다. 

즉, T(n)=T(n-1)+T(n-2)

이것은 유추를 통해서 풀 수 있다. 

항상 T(n-2)는 T(n-1)보다 작고, 두배를 해도 T(n)보다 작다.

피보나치를 계속 내려가다 보면 T(0)이 될때까지 내려가면 끝나는데, T(0)은 fib(0)을 한번만 계산하면 끝이라.. 1이다

결국, 맨 마지막 줄을 정리하면 2^(n/2)*1 가 된다. 

T(n)>2^(n/2)  이고 시간복잡도는 O(2^(n/2)).