공간복잡도 의미

• 얼마나 많은 저장 공간이 필요한지 측정하기 위한 척도
• 프로그램을 실행 및 완료하는데 필요한 저장 공간의 양을 뜻함
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
  • S(P) = c + Sp(n)
    • c : 고정공간
    • Sp(n) : 가변 공간

공간 복잡도 계산

알고리즘에서 실제 사용되는 저장 공간을 계산한다.

공간복잡도 예제1

n! 팩토리얼을 반복문으로 구하기

int factorial(n) {
  
  int fac = 1;
  
  for (int i=0; i<n; i++) {
    fac = fac * i;
  }
  
  return fac;
}

위의 경우 n의 값에 상관없이 변수n, 변수 fac, 변수 i만 필요하다. 따라서 공간복잡도는 O(1)

공간복잡도 예제2

n! 팩토리얼을 재귀함수로 구하기

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

위의 경우 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 된다. 재귀함수로 n부터 1까지 호출하였을 경우 n부터 1까지 스택에 쌓이게 된다. 따라서 공간복잡도는 O(n)