Fibonacci Sequence

- 정의

이전 두 항의 합이 다음항이 되는 수열이다.

 

- Pseudocode

// Iterative way
public static int IterFib (int n) {
    index i;
    int[] f = new int[n+1];
    
    if (n <= 0) return 0;
    
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

피보나치 수열을 구하는 알고리즘이다.

구하고자 하는 항의 값을 이전항들의 합으로 구하고 저장하는 식으로 반복한다.

n번째 항까지 반복하고 나면 n번째 인덱스에 해당하는 값을 반환한다.

 

// Recursive way
public static int RecuFib (int n) {
    if (n <= 1) return n;
    return RecuFib(n-1) + RecuFib(n-2);
}

재귀적으로 피보나치 수열을 구하는 알고리즘이다.

식은 간단하나, 함수가 과도하게 많이 호출되는 문제가 있다.

 

- Time complexity (Iterative)

Basic Operation: f[i] = f[i-1] + f[i-2];

Input Size: n (n>1)

 

* Every case: T(n) = n - 1 [Θ(n)]

 

- Time complexity (Recursive)

Basic Operation: return of RecuFiv

Input Size: n

 

* Every case:

[Θ(((1+sqrt(5)) / 2)^n)]

~= [Θ(1.6180^n)]