[알고리즘 분석] 1장. 효율, 분석, 그리고 차수 (3)

1. 피보나치(Fibonacci) 수열

 

$$ f_{0} = 0 $$
$$ f_{1} = 1 $$
$$ f_{n} = f_{n-1} + f_{n-2} $$
$$ for\ n\geq2 $$

ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
$$ f_{n} = \frac{[\frac{(1+\sqrt{5})}{2}]^{n} - [\frac{(1-\sqrt{5})}{2}]^{n}}{\sqrt{5}} $$

 

2. 피보나치 수 구하기 - 재귀적 방법(recursion)

- 문제: n번째 피보나치 수를 구하라
- 입력: 양수 n
- 출력: n번째 피보나치 수

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

 

※ 피보나치 수 구하기의 재귀적 알고리즘은 수행속도가 매우 느리다. 

- 중복으로 계산하는 피보나치 수가 존재하기 때문에

 

계산하는 항의 개수 fib_num(n) = fib_num(n-1) + fib_num(n-2) + 1

 

T(n) = fib(n)을 계산하기 위해 fib함수를 호출하는 횟수
$$ T(0) = 1 $$
$$ T(1) = 1 $$
$$ T(n) = T(n-1) + T(n-2) + 1 $$
$$ for\ n\geq2,\ n은\ 짝수 $$
$$ >2\times\ T(n-2) $$
$$ >2^{2}\times\ T(n-4) $$
$$ >2^{3}\times\ T(n-6) $$
$$ >2^\frac{n}{2}\times\ T(0) \ = \ 2^\frac{n}{2}$$
$$ for\ n\geq2,\ n은\ 홀수 $$
$$ >2\times\ T(n-2) $$
$$ >2^{2}\times\ T(n-4) $$
$$ >2^{3}\times\ T(n-6) $$
$$ >2^\frac{n-1}{2}\times\ T(1) \ = \ 2^\frac{n-1}{2}$$

 

※ 계산한 호출 횟수의 검증 - 수학적 귀납법 사용

[귀납 출발점]
$$ T(2) = T(1) + T(0) + 1 = 3 > 2^\frac{2}{2} = 2$$
$$ T(3) = T(2) + T(1) + 1 = 5 > 2^\frac{2}{2} = 2$$

[귀납 가정]
$$ 2\leq m < n 인\ 모든\ m에\ 대해서\ T(m) > 2^\frac{2}{m} \ 이라고\ 가정$$

[귀납 절차]
$$ T(n) = T(n-1) + T(n-2) + 1,\ n-1과\ n-2는\ n보다\ 작으므로\ 귀납\ 가정에\ 적용\ 가능$$
$$ T(n) > 2^\frac{n-1}{2} + 2^\frac{n-2}{2} + 1 $$
$$ > 2^\frac{n-1}{2} + 2^\frac{n-2}{2} $$
$$ = 2^\frac{n}{2} $$

 

3. 피보나치 수 구하기 - 반복적 방법

 

- 문제: n번째 피보나치 수를 구하라
- 입력: 양수 n
- 출력: n번째 피보나치 수

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 -> 0부터 n까지 한 번씩만 계산