피보나치 수열 : 왜 깡재귀로 구하면 지수 복잡도일까?

 저번 시간에는 그리디 알고리즘의 기초 문제를 다루어 보았습니다. 오늘은 피보나치 수열을 해 보도록 하겠습니다. 이 친구를 언급하기 전에, 일반항을 먼저 구해보도록 하겠습니다. 왜냐하면, 오늘 하는 내용과, 어느 정도 맞아 떨어지기 때문이에요. 먼저 피보나치 수열은 아래와 같은 관계식을 가집니다.

 

 

a(0) = a(1) = 1

a(n) = a(n-1) + a(n-2) if n>=2

 

 

 여기까지만 보면 크게 어려울 건 없어 보입니다. 그러면 어떻게 일반항을 구할까요? 2번째 식을 잘 변형해 봅시다.

 

 

a(n) - a(n-1) - a(n-2) = 0

 

 

 그러면 위와 같이 되는데요. 이를 (3)이라 합시다. 아래 꼴로 변형해 봅시다. 이걸 (4)라고 합시다.

 

 

a(n) - ta(n-1) = k(a(n-1) - ta(n-2))

 

 

 (3)과 (4)는 동치이므로, t+k = 1, tk = -1이 됩니다. t와 k는 2차 방정식 x^2 - x - 1 = 0의 두 근 중 하나가 됩니다. 하나는, (1+sqrt(5))/2, 다른 하나는 (1-sqrt(5))/2가 됩니다. 그러면 (4)가 성립하면 아래 식도 성립할까요?

 

 

a(n) - ka(n-1) = t(a(n-1) - ka(n-2))

 

 

 성립합니다. 이제, 이 둘을 적절하게 전개해 봅시다.

 

 

---

 

 (4)번 식을 전개하면 아래와 같이 나올 겁니다. 여기서 a(2) - ta(1)인데요. t = (1+sqrt(5))/2라고 하고, k = (1-sqrt(5))/2라고 해 봅시다. 그러면 a(2) - ta(1)은 k와 같기 때문에 a(n) - ta(n-1) = k^(n-1)과 같습니다. 이를 (6)번 식이라 합시다.

 

 

 마찬가지로 (5)번 식을 전개하면 다음과 같이 나오는데요. a(2) = a(1) = 1이고, k = (1-sqrt(5))/2입니다. 1 - k의 값은 (1+ sqrt(5))/2인데, 이 값은 t와 같으므로, a(n) - ka(n-1)의 값은 t^(n-1)과 같습니다. 이를 (7)번 식이라 합시다.(6)번에서 (7)번을 빼면 (k-t)a(n-1)과 k^(n-1) - t^(n-1)이 같음을 알 수 있어요. 이를 잘 정리하면

 

 

 일반항이 위와 같이 나옴을 알 수 있어요.

 

 

---

 그러면 단위 연산을 a(n)번 하는 알고리즘의 시간 복잡도는 어떻게 될까요? 단순화를 시켜 봅시다. (1+sqrt(5))/2를 A라고 하고, (1-sqrt(5))/2를 B라 합시다. 그러면 B<0이고, |B|<1입니다.

 

 

 위와 같이 그려질 겁니다. n이 커지면 커질수록, f(x)의 값은 0에 가까워 집니다. B<0이고, 정의역이 자연수라면 f(x) = B^x일 때, x가 2로 나누어 떨어지면 f(x)>0일 거고, 그렇지 않으면 f(x)<0일 겁니다. 하지만 그것과는 별개로, x가 매우 커질수록, 0에 가까워 지는 것은 부정하지 못합니다. 즉, n이 매우 크다면, A^n에 비해 B^n은 매우 작기 때문에 시간 복잡도를 계산할 때 무시해도 된다는 것입니다.

 

 

 (1+sqrt(5))/2의 값이 1.6보다 조금 큰데요. 1.6^x 그래프는 하늘색입니다. 급격하게 커집니다. x = 4일 때 값만 비교해 봐도, 주황색에 비해서 압도적으로 크다는 것을 알 수 있어요. 따라서, a(n)/a(n-1)도 (1+sqrt(5))/2로 수렴합니다. 등비 수열은 아니지만요. 여담으로, (1+sqrt(5))/2는 황금비로 잘 알려져 있는 수이기도 합니다.

 

 따라서, 수행 시간이 a(n)인 알고리즘은 복잡도가 지수급이라고 할 수 있습니다.

 

 

---

 그런데 이걸 왜 굳이 먼저 언급을 했을까요? 보통 알고리즘 교재에서 다이나믹 프로그래밍을 언급할 때 항상 드는 문제가 피보나치 수열이기 때문입니다. 아래 코드를 봅시다.

 

 

 이렇게 깡재귀로 풀면 시간 초과가 난다. 혹은 매우 오래 걸린다. 정도로 언급을 할 겁니다. 왜 그럴까요? 일단 fibo(0)과 fibo(1)은 그냥 1만 리턴하면 되기 때문에, fibo를 단 1번 호출합니다.

 

 

 그런데 n>1인 경우 이야기가 달라집니다. 함수 f(n)을 호출하고, 내부에서 또 f(n-1)을 호출하고, f(n-2)를 호출하기 때문입니다. 즉, f(n)을 불렀을 때 fibo 함수의 총 호출횟수는 먼저, f(n)을 부르는 횟수. 1번에, f(n-1)을 부르는 횟수. 이걸 T(n-1)이라 합시다. 그리고 f(n-2)를 부르는 횟수, 이걸 T(n-2)라 했을 때 T(n) = T(n-1) + T(n-2) + 1이 성립합니다.

 

 

 f(n-1)을 호출했을 때, f(n-2)와 f(n-3)을 호출을 해야 하고, 또 f(n-2)를 불렀을 때 f(n-3)과 f(n-4)를 호출해야 하기 때문이에요.  여기서 주목해야 할 것은 fibo(n-2)를 몇 번이나 중복해서 호출하는지 보시는 겁니다. 이 부분 때문에 비효율 적이라고 하는 것입니다. 그러면 이것의 일반항은 어떻게 구할까요? 이건, 두 부분으로 나눠서 구하면 그렇게 어렵지 않습니다.

 

 

 fibo(0)을 불렀을 때, fibo(1)을 불렀을 때, 호출 총 횟수는 1번입니다. 이를 0회+1회, 0회+1회로 변형해 봅시다. 그러면 fibo(2)를 호출했을 때에는, 어떻게 될까요? 일단 T(2) = T(1) + T(0) + 1이 될 건데요.

 

 

 f(n)의 노란 부분 값은 f(n-1)의 노란 부분과 f(n-2)의 노란 부분의 합을 적습니다. 그리고 윗 부분에는 T(n)과 노란 부분의 차이를 적습니다. T(2)는 3이고, f(0)의 노란 부분, f(1)의 노란 부분의 합은 2니까, f(2)의 윗 부분에 들어갈 수는 1이 됩니다.

 

 

 그러면, T(3)에 대한 정보도 다음과 같이 채워질 겁니다. f(3)의 노란 부분은 3, T(3)의 값은 5이니, f(3)의 윗 부분에 들어갈 수는 2가 됩니다. 그런데 보라색 부분과 노란색 부분의 차이가 정확히 1이네요. 노란색 부분은 대충 피보나치 수열로 가는 거 같고요.

 

 

 n>2라고 해 봅시다. 그러면 빈 칸에 무엇이 들어가야 할까요? 일단, T(n-1) = 2*F(n-1) - 1이고, T(n) = 2*F(n) - 1이였습니다. 그러면, T(n+1)은 2*(F(n-1) + F(n)) - 2 + 1입니다. 여기서 F(n-1) + F(n)은 F(n+1)입니다. 피보나치 수열이기 때문입니다. 따라서, T(n+1)은 2*F(n+1) - 1로 바꿀 수 있습니다. 파란색 + 노란색의 합이 T(n+1)이고, 노란색에 F(n+1)이 들어갔기 때문에, 파란색 부분에 들어갈 수는 F(n+1) - 1입니다.

 

 즉, fibo(x)를 호출했을 때, fibo 함수의 호출 횟수는 F(x)*2 - 1입니다. 이 때 F는 피보나치 수열을 의미합니다. F가 지수 함수급으로 증가하기 때문에, 2*F 역시 지수급으로 증가합니다. 따라서, 피보나치를 깡 재귀로 구하는 경우에, 시간 복잡도는 지수가 됩니다.

 

 

---

 만약에, 이미 구한 값을 어딘가에 저장하고 있다면 어떨까요?

 

 이 때에는 이야기가 달라집니다. fibo(20)를 알고 있는데, 다시 fibo(20)을 구하기 위해서 fibo(19)와 fibo(18)을 다시 계산하지 않습니다. fi는, 함수가 call 될 때 마다 하나씩 증가합니다.

 

 

 실제로 43번째 피보나치 항을 구할 때, 85번밖에 호출하지 않았음을 알 수 있습니다.