[파이썬][알고리즘] 공간 복잡도

공간 복잡도

• 좋은 알고리즘의 기준

  • 시간 복잡도: 얼마나 빨리 실행이 되는지에 대한 기준
  • 공간 복잡도: 얼마의 저장 공간이 필요한지에 대한 기준

• 시간과 공간은 반비례적인 경향이 있다.

• 컴퓨터 용량이 커짐에 따라서 시간 복잡도의 중요도가 중요해 졌다.

  • 빅데이터를 다루는 경우에는 공간 복잡도를 중요시 하기도 한다.

공간 복잡도

• $S(P) = c + S_p(n)$

  • c: 고정 공간
    • 알고리즘과 무관한 공간: 코드 저장 공간, 단순 변수 및 상수와 관련
  • $S_p(n)$ : 가변 공간
    • 알고리즘이 실행되면서 동적으로 필요한 공간

• 빅 오 표기법으로 생각할 때 공간 복잡도는 가변 공간에 주로 영향을 많이 받는다.

공간 복잡도 계산

• n! 구하기

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

factorial(3)

6

• 변수: n, num, i
  • O(1)

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

factorial(3)

6

• 변수: n이 n개 생긴다.
  • O(n)