Complexidade espacial

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: Google (N • L • A • I • WP refs)  • ABW  • CAPES). (fevereiro de 2026)

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: ${\displaystyle O(n),}$ ${\displaystyle O(n\log n),}$ ${\displaystyle O(n^{\alpha }),}$ ${\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 ${\displaystyle O(f(n))}$. As classes de complexidade PSPACE e NPSPACE permitem que ${\displaystyle f}$ seja qualquer polinômio, analogamente a P e NP . O que é, $${\displaystyle {\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})}$$e $${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})}$$

Referências