피보나치 수열 계산 시간 비교 (반복, 순환)

피보나치 수열 계산 시간 비교 (반복, 순환)

지난 학기에 자료구조를 배우기 시작하면서 과제로 했던 내용입니다. 쉬운 내용이지만, 그래도 도움이 되는 분이 계셨으면 좋겠습니다.

1.

.

피보나치 수열을 계산하는 프로그램을 순환하여 계산하는 방법과 반복하여 계산하는 방법을 비교해보고 성능에 차이가 생기는 원인을 알아보겠습니다.

2. 반복하여 피보나치 수열 계산하는 함수

int iterate_fib(int n)
{
    if(n<2) return n;
    else{
        int i, tmp, current = 1, last = 0;
        for(i=2; i<=n; i++){
            tmp = current;
            current += last;
            last = tmp;
        }
        return current;
    }
}

3. 순환하여 피보나치 수열 계산하는 함수

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

4.

두 함수는 n이 작을 때는 속도에 큰 차이가 없지만 순환함수의 경우 n이 조금만 커져도 속도가 아주 느려지게 됩니다.

먼저 순환함수부터 보겠습니다.

n = 35일 때 입니다.


(slow_fib 함수는 위의 recursive_fib 함수와 같습니다)

n이 겨우 35밖에 안되는데 시간은 무려 10초나 걸립니다. 반복문도 껍데기만 있을 뿐 반복하지도 않았죠.

다음으로 반복함수입니다. 실행결과를 보면

(fib_iter 함수는 위의 iterate_fib 함수와 같습니다)

무려 n = 45000 일 때를 구합니다. 거기에 그 작업을 45000번 반복합니다. 그런데 시간은 5초밖에 걸리지 않습니다. 이러한 차이는 왜 생기는 걸까요?

5.

피보나치 수는 아래와 같은 점화식으로 정의되는 수열입니다.

점화식을 보고 순환함수가 어떻게 작성되었는지 보면, 순환함수가 훨씬 정의에 가까워 보입니다. 그렇다면 순환함수를 조금 바꿔서 어떤식으로 피보나치 수열을 계산하고 있는지 출력해보겠습니다.

int recursive_fib(int n)
{
    if(n==0){
        printf("fib(%d) \n", n);
        return 0;
    }
    else if(n==1){
        printf("fib(%d) \n", n);
        return 1;
    }
    else{
        printf("fib(%d) \n", n);
        return (recursive_fib(n-1) + recursive_fib(n-2));
    }
}

이렇게 하고 n = 6을 하면 어떻게 될까요? 6번째 항을 구하기 위해서 다음과 같이 5번만 계산하면 될까요?

두번째 항 : 0 + 1 = 1
세번째 항 : 1 + 1 = 2
네번째 항 : 1+ 2 = 3
다섯번째 항 : 2 + 3 = 5
여섯번째 항 : 3 + 5 = 8

순환함수가 실제로 계산하는 과정은 다음과 같습니다.

정의대로라면 5번만 계산하면 되는 것을 순환함수는 세기도 어려울 정도로 중복되는 계산을 많이 하고 있습니다.

6.

순환함수가 저렇게 비효율적으로 계산하는 원인은 무엇일까요?

원인은 위의 그림에 나와있습니다. n=5인 경우를 구하는데 n=1인 경우를 5번이나 반복하고 있죠. 우리는 또한 바로 전에 n=6인 경우의 실행 결과에서 중복되는 경우를 살펴보았습니다.

직관적으로 보면 순환함수가 좀 더 정의에 가까운 모양을 하고 있지만 실제로는 반복함수가 효율적이고 우리가 생각하는 정의에 가까운 계산을 하고 있는 것입니다.