공간 복잡도

공간 복잡도는 입력의 특성에 따라 계산 문제의 인스턴스를 해결하는 데 필요한 메모리 공간의 양을 의미한다. 이는 알고리즘이 시작되어 종료될 때까지 사용하는 메모리의 최대량을 나타낸다. 정확한 메모리 사용 바이트 수를 계산하기보다는, 입력 크기 $n$이 변화함에 따라 메모리 요구량이 어떻게 증가하는지 분석하는 점근적 분석을 목적으로 한다.

공간 복잡도는 크게 두 가지 요소로 구성된다.

• 입력 공간: 입력 데이터를 저장하기 위해 기본적으로 필요한 메모리 공간이다.
• 보조 공간(Auxiliary Space): 알고리즘이 실행되는 동안 임시 변수 저장, 함수 호출 스택, 추가적인 자료 구조 생성 등을 위해 사용하는 공간이다.

알고리즘이 사용하는 총 공간 $S(P)$는 다음과 같이 고정 공간과 가변 공간의 합으로 정의할 수 있다.

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

• 고정 공간 ($c$): 입력 데이터의 크기와 관계없이 고정적으로 필요한 공간이다. 프로그램 코드 저장 공간, 단순 변수, 상수 등이 이에 해당한다.
• 가변 공간 ($S_p(n)$): 알고리즘 실행 과정에서 동적으로 필요한 공간이다. 실행 중에 사용하는 보조 메모리, 함수가 순환 호출(재귀)될 때 필요한 스택 공간, 추가로 생성하는 배열 등이 포함된다.

일반적으로 점근적 분석을 할 때 고정 공간은 상수로 취급되어 무시되므로, 공간 복잡도는 주로 가변 공간의 크기에 의해 결정된다.

입력 크기를 $n$이라 할 때, 주요 공간 복잡도는 다음과 같이 분류된다.

계산 복잡도 이론에서는 튜링 기계가 사용하는 공간에 따라 복잡도 계급을 정의한다.

• DSPACE(f(n)): 결정적 튜링 기계가 $O(f(n))$ 공간을 사용하여 해결할 수 있는 문제 집합이다.
• NSPACE(f(n)): 비결정적 튜링 기계가 $O(f(n))$ 공간을 사용하여 해결할 수 있는 문제 집합이다.
• PSPACE: 임의의 다항식 크기 공간을 사용하여 해결할 수 있는 문제들의 집합이다. $PSPACE = \bigcup_{c \in \mathbb{Z}^+} DSPACE(n^c)$와 같이 정의된다.
• NPSPACE: 비결정적 튜링 기계에 대한 다항식 공간 문제 집합이다. 사비치 정리(Savitch's theorem)에 따르면 $NPSPACE = PSPACE$가 성립한다.

알고리즘 설계 시 시간 복잡도와 공간 복잡도는 대개 반비례 관계(Trade-off)를 가진다. 메모리를 더 많이 사용하여 실행 시간을 단축하거나(예: 동적 계획법의 메모이제이션), 반대로 실행 시간을 늘려 메모리 사용량을 줄이는 방식이 사용된다.

현대 컴퓨팅 환경에서는 하드웨어의 발전으로 메모리 용량이 풍부해짐에 따라 시간 복잡도를 더 우선시하는 경향이 있다. 그러나 임베디드 시스템이나 대규모 데이터 처리 환경에서는 여전히 공간 효율성이 중요한 지표로 다뤄진다.