[알고리즘] 공간 복잡도

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있다.
• 시간 복잡도: 얼마나 빠르게 실행되는지
• 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

• 통상 둘 다 만족시키기 어려움
• 시간과 공간은 반비례적 경향이 있다
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선이 된다.

 

공간 복잡도(Space Complexity)

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
• 고정 공간(알고리즘과 무관한 공간): 코드 저장 곤간, 단순 변수 및 상수
• 가변 공간(알고리즘 실행과 관련이 있는 공간): 실행중 동적으로 필요한 공간
• 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛)
• c: 고정 공간
• 𝑆𝑝(𝑛): 가변 공간

Big-O 표기법을 생각해볼 때 고정공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.

 

공간 복잡도 계산

• 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.

ex) 재귀함수를 사용하지 않은 factorial함수

• 변수 n의 값에 상관없이 변수 n, 변수 result, 변수 index만 필요로하기 때문에 공간복잡도는 O(1)이 된다.

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

 

ex) 재귀함수를 사용한 factorial함수

• factorial함수를 재귀 함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 되어 저장공간이 n개 만들어지게 되므로 공간복잡도는 O(n)이 된다.

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