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 . 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.