[자료구조] 공간 복잡도

알고리즘 복잡도는 시간 복잡도가 우선이지만, 공간 복잡도의 대략적인 계산이 필요할 때도 있다.

• 빅 오 표기법에 따라, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.
• 공간 복잡도는 알고리즘에서 실제 사용되는 변수를 고려하여 빅 오 표기법으로 표현

예제1

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

• 알고리즘에 상관없이, 변수는 (n, fac, index)만 필요
• 공간 복잡도 : O(1)

예제2

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

• 알고리즘에 따라, 변수 n이 n개가 필요
• 공간 복잡도 : O(n)