#include
int result=0;
int fibonachi(int n)
{
if(n==0) return 0;
else
{
if(n==1||n==2) return 1;
result = fibonachi(n-1)+fibonachi(n-2);
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",fibonachi(n));
return 0;
}
일반 피보나치 알고리즘이 시간복잡도가 크다는 건 이해가 가는데
근데 배열로 해도 똑같이 시간복잡도가 큰거 아니여?
연산은 둘다 똑같은거 같은데 ㄹㅇ..
배열로 하면 실행시간이 훨씬 짧아진다는게 이해가 잘 안감.
#include
long long int fibonachi(int n)
{
static long long int result[200]={};
if(n==0) return result[0]=0;
if(n==1) return result[1]=1;
if(result[n]>0) return result[n]; // 0으로 초기화해서 값이 입력되면 바로 리턴.
return result[n]=fibonachi(n-1)+fibonachi(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%lld",fibonachi(n)009);
return 0;
}
메모이제이션 버전은 한번 계산이 끝난걸 다시 쓰잖아요 fibo(4)=fibo(2)+fibo(3), fibo(3)=fibo(1)+fibo(2), fibo(2)=fibo(0)+fibo(1) fibo(4)를 호출한다고하면 fibo(2)를 구하는 과정과 fibo(3)을 구하는 과정에서 fibo(1)과 fibo(2)는 이미 fibo(2)에서 계산이 됐는데
fibo(3)에서 또 fibo(2) 재귀를 타면서 구하잖아요 배열로 캐싱해서 이미 구한값을 재활용하니까 재귀를 안타고 바로 계산된 값을 쓰니까 더 빠르죠