[알고리즘] 시간복잡도와 공간복잡도 (2)

이번에는 공간복잡도에 대해 알아보겠습니다.

2. 공간 복잡도

공간 복잡도는 프로그램 실행 후, 완료하는데까지 필요로하는 자원의 양을 나타냅니다.

크게는 고정공간과 가변 공간으로 나눌 수 있습니다.

고정 공간은 단순 변수 및 상수이고, 가변 공간은 실행 중에 동적으로 필요한 공간을 말합니다.

일반적으로는 시간 복잡도와 공간 복잡도는 반비례적 경향이 있습니다.

그렇기 때문에 대부분 시간 복잡도 위주로 판단을 합니다.

이번에는 예제를 통해서 공간 복잡도를 계산해보겠습니다.


ex1) n! 팩토리얼의 공간복잡도 ( 재귀 )

n! = 1 x 2 x ... x n

위 팩토리얼의 경우, 재귀 함수를 통해서 구현이됨.

재귀 함수의 경우, n값에 상관없이 몇 가지 몇수들만 필요하기 때문에 공간복잡도는 O(1)

공간 복잡도는 실제 실행했을 때 사용되는 저장공간으로 계산

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

위의 경우, 재귀 함수는 n만큼 수행되기 때문에 변수n이 n개만큼 만들어짐

-> 공간 복잡도는 O(n)


ex2 ) n! 팩토리얼의 공간복잡도 ( 반복 )

위 팩토리얼의 경우 반복문으로 구현이 됨.

int factorial(int n)
{
    int result = 1, idx = 0;

    for ( idx = 1 ; idx < n + 1 ; idx++ )
        result*=idx;

    printf("%d! = %d\n", n, result);
}

반복문이기 때문에 변수는 고정으로 쓰고, 새로운 변수가 추가되지 않음

값이 바뀌는 것은 공간에 영향을 미치지 않음.

->공간 복잡도는 O(1)

이상입니다.