[C] 시간복잡도가 O(n)인 재귀함수로 피보나치 수열 구하기

 앞으로 2학년 때 들었던 자료구조 수업의 내용들을 복습해보려고 한다. 그 학기에 배웠던 여러 과목 중에 가장 어려웠고, 그만큼 중요한 수업이기 때문이다. 오늘은 그 첫 번째로 C언어를 이용해 시간복잡도가 O(n)인 재귀 구조의 피보나치수열을 만들었던 것을 살펴보려고 한다.

 

1. 시간복잡도가 O(n^2)인 경우

 피보나치 수열을 구현하는 방법은 재귀 함수, 반복문 두 가지가 있다. 그중 재귀함수를 이용해 피보나치수열을 구하면 일반적으로 O(n^2)의 시간복잡도를 가진다. 

long long fib(int n) {
  if ( n <= 1 ) { //1번째, 2번째 피보나치 수(0,1)
    return n;
  }
   
  return fib(n-1) + fib(n-2);
}

 

T(n)을 피보나치수열의 n번째 숫자를 계산하기 위한 연산 횟수라고 하면  T(0) = 1, T(1) = 1이다. 또한 T(n-1) > T(n-2) 임으로, 2 이상의 n에 대하여 다음이 성립한다.

T(n) = T(n-1) + T(n-2) + 1 > 2 x T(n-2) > 2^2 x T(n -4).... > 2^n/2 x T(0) = 2^n/2

 

따라서 위 알고리즘의 시간복잡도는 O(2^n)이다.

 

 

2. 시간복잡도가 O(n)인 경우

long long fib(int n) { 
	long long a[100] = { 0, 1, };
	if (n < 2 || a[n] != 0) { // 해당 피보나치 수를 이미 구한 경우
		return a[n];
	}

	else { // 피보나치 수를 아직 구하지 않은 경우
		a[n] = fib(n - 1) + fib(n - 2);
		return a[n];
	}
}

피보나치 수를 구하면 배열에 저장해 두고, 필요할 때는 배열에서 불러왔다. 이렇게 이미 구한 값을 메모리에 저장해두고 다시 사용하는 기법을 메모이제이션(memoization)이라고 한다.  

 

위 방법의 시간복잡도를 구해보면 

T(0) = 1, T(1) = 1이고

T(2) = T(1) + T(0) + 1 = 3

T(3) = T(2) + T(1) + 1 = 5

T(4) = T(3) + T(2) + 1에서 T(2)는 저장한 피보나치 수를 가져오기만 하면 되기 때문에 T(2) = 1이다. 따라서 T(3) + T(2) + 1 = 7이고, 같은 이유로 T(5) = T(4) + T(3) + 1에서 T(3) = 1이므로 T(5) = 9이다. 따라서 T(n) = 2n - 1이라고 할 수 있고, 시간복잡도는 O(n)이다.