A complexidade espacial de um algoritmo ou de uma estrutura de dados é o tanto de espaço na memória necessário para resolver uma instância do problema computacional como uma função das características da entrada. É a memória que um algoritmo requer até que execute completamente. Isso inclui o espaço de memória utilizado por suas entradas, chamado de espaço de entrada, e qualquer outra memória (auxiliar) que ele use durante a execução, que se chama espaço auxiliar . Parecido com a complexidade temporal, a complexidade espacial é muitas vezes expressa assintoticamente na notação O-grande, como por exemplo:
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}),}
etc, onde n é uma característica da entrada influenciando a complexidade espacial.
Classes da complexidade espacial Analogamente às classes da complexidade temporal DTIME(f(n)) e NTIME(f(n)), as classes de complexidade DSPACE(f(n)) e NSPACE(f(n)) são os conjuntos de linguagens que podem ser decididas por máquinas de Turing determinísticas (respectivamente, não determinísticas) que utilizam espaço
O ( f ( n ) )
{\displaystyle O(f(n))}
. As classes de complexidade PSPACE e NPSPACE permitem que
f
{\displaystyle f}
seja qualquer polinômio, analogamente a P e NP . O que é,
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})}
e
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})}
Referências