[자료구조] 피보나치 수열

순환의 세번째 주제인 피보나치 수열은 앞의 두 개의 숫자를 더해 뒤의 숫자를 만드는 것이다.

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

 

순환으로 구현하면 다음과 같다.

int fibonacci(int n) {
	if (n == 0) return 0;
    	if (n == 1) return 1;
    	return fibonacci(n-1) + fibonacci(n-2);
}

 

실제로, fibonacci(5) 를 구현하면 다음과 같다.

fibonacci(5) 호출

fibonacci(4) 호출

fibonacci(3)  호출

fibonacci(2) 호출

fibonacci(1) 호출

fibonacci(0) 호출

fibonacci(1) 호출

fibonacci(0) 호출

fibonacci(2) 호출

fibonacci(1) 호출

fibonacci(0) 호출

fibonacci(3) 호출

fibonacci(2) 호출

fibonacci(1) 호출

fibonacci(0) 호출

fibonacci(2) 호출

fibonacci(1) 호출

fibonacci(0) 호출

 

순환 구조는 호출할 수록 문제의 크기가 작아져야 한다. 하지만 피보나치 수열을 순환적으로 계산하면

오히려 문제가 2배로 늘어난다. 따라서 시간복잡도는 O(2^n)이다.

 

반복적인 구조로 표현한다면 시간복잡도를 줄일 수 있을까?

반복 구조로 구현하면 다음과 같다.

int fibonacci(int n) {
	if (n == 0) return 0;
    	if (n == 1) return 1;
    
    	int pp = 0;
    	int p = 1;
    	int result = 0;
    
    	for (int i = 2; i<n; i++) {
    		result = pp + p;
            	pp = p;
            	p = result;
        }
    	return result;
}

 

반복 구조의 시간복잡도는 O(n)으로 순환 구조보다 훨씬 빠르다.