Fibonacci | 피보나치 수열

각 항이 그 앞의 두 항의 합인 수열.
만든 사람이 이탈리아 수학자 피보나치(Fibonacci).

• 피보나치 수열
  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) (n ≥ 2)
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Recursion | 재귀

int RecFib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return RecFib(n - 1) + RecFib(n - 2);
}

중복된 연산이 계속 발생해서 O(1.618^N)의 시간복잡도를 가진다.
재귀 호출이 많아질수록 (N이 클수록) 스택 오버플로우(Stack Overflow) 위험이 증가한다.

DP

int DpFib(int n)
{
    int[] D = new int[n + 1];
    D[0] = 0;
    D[1] = 1;

    for (int i = 2; i <= n; i++)
        D[i] = D[i - 1] + D[i - 2];

    return D[n];
}

미리 배열을 만들어두고 0~N까지 하나씩 채워가는 방식.
N+1칸을 채우고 나면 답(N)을 알 수 있으니 O(N)의 시간복잡도를 가진다.

Iterative | 반복문

int IterativeFib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

반복문을 이용한 방식.
마찬가지로 O(N)의 시간복잡도를 가지지만, 배열을 사용하지 않아 메모리를 덜 사용한다.
O(1)의 공간복잡도를 가진다.

Comparsion

중간 결과 저장/이용 유무에 따라 극적인 시간복잡도의 차이가 발생한다.