알고리즘 이나 자료 구조 의 공간 복잡도 (空間複雜度, space complexity)는 입력의 특성에 따라 계산 문제 의 인스턴스를 해결하는 데 필요한 메모리 공간의 양이다. 이는 알고리즘이 완전히 실행될 때까지 필요한 메모리이다. 여기에는 입력 공간이라고 하는 입력에 사용되는 메모리 공간과 실행 중에 사용하는 다른 (보조) 메모리(보조 공간이라고 함)가 포함된다.
시간 복잡도 와 마찬가지로 공간 복잡도는
O
(
n
)
,
{\displaystyle O(n),}
O
(
n
log
n
)
,
{\displaystyle O(n\log n),}
O
(
n
α
)
,
{\displaystyle O(n^{\alpha }),}
O
(
2
n
)
,
{\displaystyle O(2^{n}),}
대문자 O 표기법 으로 점근적으로 표현된다. 여기서 n 은 공간 복잡도에 영향을 미치는 입력의 특성이다.
시간 복잡도 계급 DTIME(f(n)) 및 NTIME(f(n)) 과 유사하게 복잡도 계급 DSPACE(f(n)) 와 NSPACE(f(n)) 은
O
(
f
(
n
)
)
{\displaystyle O(f(n))}
PSPACE 및 NPSPACE 는 P 와 NP 와 유사한 임의의 다항식이 될 수 있다. 즉,
P
S
P
A
C
E
=
⋃
c
∈
Z
+
D
S
P
A
C
E
(
n
c
)
{\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}
N
P
S
P
A
C
E
=
⋃
c
∈
Z
+
N
S
P
A
C
E
(
n
c
)
{\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}
공간 계층 이론 에 따르면 공간 구성이 가능한 모든 함수
f
(
n
)
{\displaystyle f(n)}
f
(
n
)
{\displaystyle f(n)}
f
(
n
)
{\displaystyle f(n)}
복잡도 계급 간에는 다음과 같은 포함 관계가 성립한다.
D
T
I
M
E
(
f
(
n
)
)
⊆
D
S
P
A
C
E
(
f
(
n
)
)
⊆
N
S
P
A
C
E
(
f
(
n
)
)
⊆
D
T
I
M
E
(
2
O
(
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)}
또한 사비치 정리 에 따라
f
∈
Ω
(
log
(
n
)
)
{\displaystyle f\in \Omega (\log(n))}
N
S
P
A
C
E
(
f
(
n
)
)
⊆
D
S
P
A
C
E
(
(
f
(
n
)
)
2
)
{\displaystyle {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right)}
직접적인 따름정리로
P
S
P
A
C
E
=
N
P
S
P
A
C
E
{\displaystyle {\mathsf {PSPACE}}={\mathsf {NPSPACE}}}
지수 시간 가설 은 시간 복잡도에 대해 결정론적 복잡도와 비결정론적 복잡도 사이에 기하 급수적인 차이가 있을 수 있다고 추측한다.
