공간 복잡도 문서 원본 보기

{{위키데이터 속성 추적}}
[[알고리즘]]이나 [[자료 구조]]의 '''공간 복잡도'''(空間複雜度, space complexity)는 입력의 특성에 따라 [[계산 문제]]의 인스턴스를 해결하는 데 필요한 메모리 공간의 양이다. 이는 알고리즘이 완전히 실행될 때까지 필요한 메모리이다. 여기에는 입력 공간이라고 하는 입력에 사용되는 메모리 공간과 실행 중에 사용하는 다른 (보조) 메모리(보조 공간이라고 함)가 포함된다.

[[시간 복잡도]]와 마찬가지로 공간 복잡도는 <math>O(n),</math>
<math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math>와 같은 [[대문자 O 표기법]]으로 점근적으로 표현된다. 여기서 {{mvar|n}}은 공간 복잡도에 영향을 미치는 입력의 특성이다.

== 공간 복잡도 계급 ==
시간 복잡도 계급 [[DTIME|DTIME(f(n))]] 및 [[NTIME|NTIME(f(n))]]과 유사하게 복잡도 계급 [[DSPACE|DSPACE(f(n))]]와 [[NSPACE|NSPACE(f(n))]]은 <math>O(f(n))</math> 공간을 사용하는 결정적 및 비결정적 튜링 기계에 의해 결정 가능한 언어 집합이다. 복잡도 계급 [[PSPACE]] 및 [[NPSPACE]]는 [[P (복잡도)|P]]와 [[NP (복잡도)|NP]]와 유사한 임의의 다항식이 될 수 있다. 즉,
<math display=block>\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)</math>
및
<math display=block>\mathsf{NPSPACE} = \bigcup_{c \in \Z^+} \mathsf{NSPACE}(n^c)</math>
이다.

== 계급 사이의 관계 ==
[[공간 계층 이론]]에 따르면 공간 구성이 가능한 모든 함수 <math>f(n)</math>에 대해 메모리 공간 <math>f(n)</math>을 가진 기계로 풀 수 있지만, 점근적으로 <math>f(n)</math>보다 작은 메모리 공간을 가진 기계는 풀 수 없는 문제가 존재한다.

복잡도 계급 간에는 다음과 같은 포함 관계가 성립한다.
<math display=block>\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)</math>

또한 [[사비치 정리]]에 따라 <math>f \in \Omega(\log(n))</math>인 경우 아래의 역의 포함 관계가 성립한다.
<math display=block>\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right)</math>

직접적인 따름정리로 <math>\mathsf{PSPACE} = \mathsf{NPSPACE}</math>이 성립한다. 이 결과는 비결정적 기계가 문제를 해결하는 데 필요한 공간을 조금만 줄일 수 있다는 결과를 뜻하기에 암시하기에 놀랍다. 대조적으로, [[지수 시간 가설]]은 시간 복잡도에 대해 결정론적 복잡도와 비결정론적 복잡도 사이에 기하 급수적인 차이가 있을 수 있다고 추측한다.

== 같이 보기 ==
* [[L (복잡도)]]

[[분류:계산 복잡도 이론]]
[[분류:계산 자원]]