공간 복잡도

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

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

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

공간 계층 이론에 따르면 공간 구성이 가능한 모든 함수 ${\displaystyle f(n)}$에 대해 메모리 공간 ${\displaystyle f(n)}$을 가진 기계로 풀 수 있지만, 점근적으로 ${\displaystyle f(n)}$보다 작은 메모리 공간을 가진 기계는 풀 수 없는 문제가 존재한다.

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

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

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

• L (복잡도)