알고리즘 시간복잡도 구하는 법 ( 반복대치 )

#include <stdio.h>

factorial(int n)
{
    if(n == 1) return 1;        //1
    return n * factorial(n-1);  //2
}

시간복잡도 : T(n) = T(n-1) + c        ( c는 "1의 수행시간 + 2에서의 곱셈의 수행시간" )

 

위의 factorial() 함수의 시간복잡도를 반복대치를 이용해 구해보겠다.

 

반복대치

T(n) = T(n-1) + c

      = T(n-2) + 2c

      = T(n-3) + 3c

      . . .

      = T(1) + (n-1) * c

 

이때, n = 1일 때 T(1)은 1의 수행시간 밖에 들지 않으므로  1의 수행시간 + 2의 수행시간의 값을 가지는 c보다 작다.
     <= c + (n-1) * c
     <= nc

 

즉, 빅오의 정의에 의해 T(n) = O(n)이 된다.

 

=> 재귀함수의 시간복잡도 : O(n)