recursion/memoization 복잡도에 대해

1. 개요

  Fibonacci Algorithm 을 recursive call, recursive call with memoization 을 이용하여 이 두가 지를 각각 프로그램하고 수행시간을 측정하고 그 결과를 그래프를 이용하여 비교하여 관찰 한다.

 

2. Fibonacci Algorithm 의 두 코드에 대한 Pseudo code

    2.1 recursive call Pseudo code

     fib(n) {
            if n is 1 or 2, return 1;

            return fib(n-1) + fib(n-2);

     }

    2.2 recursive call with memoization Pseudo code

      fib(n) {
                if memo[n] is zero;

                memo[n] = fib(n-1) + fib(n-2);

                return memo[n];

    }

 

3. recursive call

     3.1 code

#include<stdio.h>
#include<time.h>

long fib(int n)
{
    if (n < 2) return n;
    return(fib(n - 1) + fib(n - 2));
}

int main() {
    clock_t t;
    for (int i = 0; i < 46; i++) {
        t = clock();
        long a = fib(i);
        printf("%d 번 째 연산 결과 값: %d\n",i+1, a);
        t = clock() - t;
        printf("[%f seconds] \n", ((float)t) / CLOCKS_PER_SEC);
    }
}

     3.2 recursive call result

 

 

4. recursive call with memoization

     4.1 code

#include<stdio.h>
#include<time.h>
long Memo[9999999];
long fib(int n)
{
    if (n < 2) return n;
    if (Memo[n] != 0) return Memo[n];
    Memo[n] = fib(n - 1) + fib(n - 2);
    return Memo[n];
}

int main() {
    clock_t t;
    for (int i = 0; i < 46; i++) { t = clock();
        long a = fib(i);
        printf("%d 번째 연산 결과 값 : %ld\n", i, a);
        t = clock() - t;
        printf("[%f seconds] \n", ((float)t) / CLOCKS_PER_SEC); }
}

 

     4.2 recursive call with memoization result

 

 

 

5. memoization 의 유무에 따른 시간 비교

 

6. 관찰의견 및 결론

 

  Memoization 의 유무에 따른 시간 비교를 보면 초기부터 22 번째까지의 시간은 차이가 나 지 않지만 그 이후부터 두 프로그램의 수행 시간의 차이는 exponential 하게 차이가 난다.

이는 반복적 연산이 때마다 모든 함수에 대한 계산을 하기 때문인데, 피보나치 수열의 경 우 수열이 반복 될수록 결과가 어마어마하게 증가하게 된다. 실제 연산을 46 이상 넘어가게 되면 프로그램을 실행하기도 힘들 정도의 시간을 소요하게 되며, 이후 48 번째 계산을 넘어 가게 되면 피보나치 결과 값이 너무 커져 float안에 값을 저장할 수 없어 음수 혹은 예상치 못한 결과로 치명적인 버그가 발생하게 된다. 이러한 버그와 수행 속도를 향상하기 위해 memoization 을 사용한다.

Memoization 은 프로그램이 동일한 계산을 반복해야 수행할 때, 그 전에 할당된 함수를 반복적으로 불러와 연산을 하는 반복적 연산과는 달리 이전의 계산된 값을 메모리에 저장 함으로써 동일한 계산을 반복하지 않고 메모리의 값을 불러와 순환적으로 연산하는 방법이 다. 따라서 이는 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 할 수 있다.

컴퓨터 프로그램은 수행 시간을 줄일 수록 아주 효과적인 프로그램이라고 할 수 있는데 위와 같은 memoization 의 특성들을 활용하여 검색 시간, 파일의 압축과 변환과 같은 반복 적인 계산 혹은 비슷한 패턴의 분석과 처리에 활용할 수 있을 것이라 생각된다.