Complexidade espacial
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.
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})}
