[알고리즘] 피보나찌 수 구하기

피보나찌 수 구하기

피보니찌

• 재귀 함수의 한계를 설명하기 좋음
• n(n ≥ 2)의 피보나찌 = (n-2) + (n-1)

1. 재귀적 방법으로 피보나찌 수 구하기

• n-1과 n-2의 값이 1 또는 0이 될 때 까지 fib 함수가 재귀적으로 호출된다.

int fib(int n) {
	if (n <= 1)
		return n;
	else
		return(fib(n-1)+fib(n-2));
}

 

• fib(5)를 계산 ⇒ fib(2)는 3번 중복계산, fib(1)는 5번 중복계산 …
• 같은 수를 중복 계산 ⇒ 비효율적!

fib(n)의 함수 호출 횟수 계산

• T(n) : fib(n)을 계산하기 위하여 fib 함수를 호출하는 횟수 즉, 재귀 트리 상의 노드의 개수

T(n) = T(n - 1) + T(n - 2) +1 (for n ≥ 2)
> 2 x T(n - 2)         → 왜냐하면 T(n - 1) > T(n - 2) 
> 2^2 x T(n - 4)
> 2^3 x T(n - 6)
…
2n/2 x T(n-n) = 2n/2xT(0) = 2^n/2

결론

재귀적 알고리즘으로 구성한 재귀 트리의 노드 수를 T(n)이라 하면, n2인 모든 n에 대하여 T(n)> 2n/2 이다. ⇒ 매우 느림

이유: 같은 피보나찌 수를 중복 계산

2. 반복적 방법으로 피보나찌 수 구하기

int fib2 (int n) 
{ index i;
	int f[0..n];
	f[0]=0;
	if (n>0) 
	{
		f[1]=1;
		for (i=2; i<=n; i++)
			f[i]= f[i-1]+f[i-2];
	}
	return f[n];
}

반복 알고리즘에서 계산하는 항의 총 개수

T(n) = n + 1 

즉, f[0]부터 f[n]까지 한번씩 만 계산

결론

피보나찌 수 문제에서 반복 알고리즘은 재귀 알고리즘보다 수행속도가 훨씬 더 빠르다.
이유: 중복 계산이 없음