피보나치 수열과 Big-O 표현

피보나치 수열 (Fibonacci Sequence)과 Big-O 표현

13세기 이탈리아 수학자 Leonardo Fibonacci가 만든 수열은 널리 알려져 있다.
피보나치 수열은 직전 2개의 수를 합한 값이 현재 값이 되도록 전개된다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., 

조금 더 수학적으로 쓰면 수열 $F_n$은 다음과 같은 수식으로 표현할 수 있다.

$F_n = \begin{cases} {F_{n-1} + F_{n-2}} &\text{if n > 1}\\ 1 &\text{if n = 1}\\ 0 &\text{if n = 0}\\ \end{cases}$

피보나치 수열은 2의 지수승 정도의 속도로 증가하고, $F_{30}$에서 이미 21자리수를 돌파한다. 일반적으로 피보나치 수열의 성장 속도는 $F_{n} \approx 2^{0.694n} \approx (1.6)^n$으로 알려져 있다.

알고리즘

지수 알고리즘 (Exponential algorithm)

$F_{n}$을 재귀적(Recursive)으로 정의 하면 다음과 같이 표현이 가능하다.

function fib1(n)
   if n=0: return 0
   if n=1: return 1
   return fib1(n-1) + fib1(n-2)

알고리즘을 볼 때, 항상 다음 3개의 질문에 대한 답을 항상 생각해야한다.

1. 알고리즘이 옳은가?
2. 얼마나 오래 걸리는가? (n에 대한 함수로 표현)
3. 더 잘 할 수 있는가?

위에 정의한 Fib1 알고리즘은 1번 질문에 대해서 피보나치 수열의 정의를 잘 따르고 있다.
두번째 질문에 대한 대답을 하기 위해서, Fib1(n)을 계산하는데 필요한 계산단계(step)을 세는 $T(n)$이라는 함수를 정의 할 필요가 있다. Fib1(n)에 대해서 2보다 작은 경우 즉시 답을 얻을 수 있다.

$T(n) \leq 2 \quad for \quad n \leq 1$

큰 값을 가지는 n에 대해서, fib1(n)은 2개의 재귀 호출부로 구성되면, 각 호출부는 $T(n-1)$과 $T(n-2)$의 계산단계를 필요로 한다. 따라서 1보다 큰 n에 대해서 $T(n)$은 아래와 같이 표현이 가능하다

$T(n) = T(n-1) + T(n-2) + 3 \quad for \quad n >1$

$T(n)$의 형태를 잘 살펴 보면 $T(n)$이 $F_n$보다 더 크다는 걸 알수가 있다. ($T(n)$은 각 스텝 마다 +3이 있다).
이건 정말 곤란한 상황이다. 수열의 값을 알기 위한 알고리즘을 계산하는데 걸리는 시간이 수열 자체와 비슷하게 증가하는 상황이다. $F_{200}$을 계산 하기 위해서는 $T(200) \geq F_{200} \geq 2^{138}$의 계산 단계를 거쳐야 한다. NEC Earth Simulator(아마도 책을 쓸 당시에는 세계에서 제일 좋은 컴퓨터)에서도 $2^{92}$초의 시간이 걸린다.
자!! 그럼 어떻게 하면 이 알고리즘을 더 빠르게 계산 할 수 있는지에 대한 세번째 대답을 할 시점이다.

다항 알고리즘 (Polynomial algorithm)

먼저 다른 알고리즘을 설계 하기 전에 Fib1(n)이 왜 이렇게 느린 알고리즘인지 원인을 분석 할 필요가 있다. 먼저 Fib1이 느린 이유는 cascade recursive invocation이라 불리는 것이다. 즉, 재귀적으로 돌면서 계속적으로 다른 함수를 호출 한다. 즉, 똑같은 짓을 계속 반복해서 한다는 것이다.
그러면 이 문제를 해결 할 방법은 없을까?
이미 한번 계산 한것은 **다시 계산하지 않도록 저장을 해두는 것이다. **

function fib2(n)
   if n=0: retrun 0
   create an array f[0,...,n]
   f[0] = 0, f[1] =1
   for i = 2...n:
     f[i] = f[i-1] + f[i-2]
   return f[n]

새롭게 만든 Fib2에서도 앞서 말한 3가지 질문을 다시 해보자.
옳은가? 수식이 보여주듯이 자체적으로 Fibonacci 수열의 정의를 따른다.
loop안에 구문을 보면 1단계의 스텝으로 이루어져 있고, 이게 n-1번 반복된다.
즉, Fib2의 수행에 걸리는 시간은 n에 비례하는 1차 다항식을 따른다. (linear in n)
지수 함수 비례 관계를 가지는 Fib1에 비하면, Fib2는 매우 빠르다.
심지어 $F_{200}$이 아니라 $F_{200,000}도 계산이 가능하다.

이론적으로 Fib2는 1차 다항식을 따라야 한지만, 과연 그럴까?
사실 그렇지는 않다.
현재 우리가 쓰는 컴퓨터는 32bit 또는 64bit까지만 숫자를 표현 할 수 있는데, 그 자리수를 넘어가면, 컴퓨터에서 수를 다루는 방법이 달라져야 한다. 이러한 변경은 Fib2가 느려지는 결과를 가지고 온다.

그렇다면 Fib2보다 더 좋은 알고리즘을 만들 수 있을까? (가능하다, Matrix 연산을 쓰도록 하자)

Big-O 표현 (Big-O notation)

알고리즘이 계산되는데 필요한 스텝의 수를 세는 것 보다 효과적으로 알고리즘이 걸리는 시간을 간단하게 표현할 방법이 없을까?
사실 필요한 단계 수를 세는것 자체가 이미 단순화 작업을 거친 것의 결과물이다.
컴퓨터에서 모든 구문이 동일한 시간에 끝나는 것은 아니다.
그래도 $5n^3 + 4n + 3$ 단계로 표현하는건 귀찮고, n이 커지면 커질 수록 뒤에 디테일은 그렇게 중요하지도 않다. 이 수식에서 가장 큰 덩어리를 차지하는 것은 $5n^3$ 부분이다.
그리고 5라는 상수도 $n^3$을 알면 된다.
즉, 위 수식에서 가장 중요한 것은 $n^3$가 얼마나 큰 수인지 아는 것이다.
이런식으로 알고리즘이 걸리는 시간을 표현한 것이 Big-O 표현이다.
즉, 제일 중요한 것만 남기고 나머지는 과감하게 단순화 시켜 버리는 것이다.
$5n^3 + 4n + 3$을 Big-O 노테이션으로 표현하면, O($n^3$)가 된다.

참고 문헌에 나온 정의는 다음과 같다.

Let f(n) and g(n) be functions from positive integers to positive reals. 
We say f = O(g) (which means that "f grows no faster than g")
if there is a constant c > 0 such that f(n) <= c*g(n)

두개의 함수 $f_1(n) = n^2$, $f_2(n) = 2n + 20$ 를 생각 해보자.
Big-O notation으로 쓸 때, $f_2 = O(f_1)$으로 표현하는 것이 가능하다.
왜냐면 두함수의 비율이 22를 넘을 수 가 없기 때문이다.
$\frac{f_2(n)}{f_1(n)} = \frac{2n+20}{n} \leq 22$
초반에는 $f_1(n)$이 조금 더 크지만, 어느 순간 $f_2$가 더 커지게 된다.
즉 반대로, $f_1 = O(f_2)$ 을 쓸 수 없다.
비슷하게, $f_3(n) = n+1$ 은 $f_3 = O(f_2)$로 표현이 가능하다.

비슷하게 $f=\Omega(g)$와 $f=\Theta(g)$ 라는 표현이 있다.

$f=\Omega(g)\quad means \quad g = O(f)\\ f=\Theta(g)\quad means \quad f=O(g)\quad and \quad g = O(f)$

즉, f가 g보다 빠르게 자랄때, 즉 O와 역관계일 때 $\Omega$를 사용할 수 있다.
자라는 속도가 같을때는 $\Theta$를 사용 할 수 있다.
위의 예제에서 $f_2 = \Theta(f_3)$이고, $f_1 = \Omega(f_3)$로 표현이 가능하다.

후기 - 이거 글로 쓰는거 쉽지 않네요. 그래도 쓰다보니까 좀 더 잘 이해가 되는거 같기도 하고… 계속 한번 적어보도록 하겠습니다.
업데이트 속도는 기대하지 마세요. 아마도 최소 2-3년은 걸릴거 같기도 하네요.
보시는 분이 있을지는 모르겠지만…