공간 복잡도

---

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
• 일반적으로 시간 복잡도와 공간 복잡도는 반비례적이다.
• $S(P) = c + S_p(n)$
  • c : 고정 공간
  • S : 가변 공간
  • 고정 공간은 상수이다. 그러므로 가변 공간에 의해 공간 복잡도가 결정된다.

공간 복잡도 계산

---

예제 1

• n! 팩토리얼 구하기
  • n의 값에 상관없이 변수 n, fac, index만 필요하다.
  • 위의 변수들은 고정 공간이므로 $O(3)$ -> $O(1)$ 이다.

def factorial(n):
    fac = 1
    for index in range(2, n + 1):
        fac = fac * index
    return fac

예제 2

• n! 팩토리얼 구하기
  • 변수는 n 한 개이다. 하지만 재귀함수를 사용하였으므로, 변수 n이 n번 호출된다.
  • $O(1) * n$ -> $O(n)$ 이다.

def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1