DAA - Complexidades Espaciais

Neste capítulo, discutiremos a complexidade dos problemas computacionais com relação à quantidade de espaço que um algoritmo requer.

A complexidade do espaço compartilha muitas das características da complexidade do tempo e serve como outra forma de classificar os problemas de acordo com suas dificuldades computacionais.

O que é a complexidade do espaço?

A complexidade do espaço é uma função que descreve a quantidade de memória (espaço) que um algoritmo leva em termos da quantidade de entrada para o algoritmo.

Costumamos falar de extra memorynecessário, sem contar a memória necessária para armazenar a própria entrada. Novamente, usamos unidades naturais (mas de comprimento fixo) para medir isso.

Podemos usar bytes, mas é mais fácil usar, digamos, o número de inteiros usados, o número de estruturas de tamanho fixo, etc.

No final, a função que criarmos será independente do número real de bytes necessários para representar a unidade.

A complexidade do espaço às vezes é ignorada porque o espaço usado é mínimo e / ou óbvio, no entanto, às vezes torna-se uma questão tão importante quanto a complexidade do tempo

Definição

Deixei M seja um determinista Turing machine (TM)que pára em todas as entradas. A complexidade do espaço deM é a função $ f \ colon N \ rightarrow N $, onde f(n) é o número máximo de células da fita e M verifica qualquer entrada de comprimento M. Se a complexidade do espaço deM é f(n), Nós podemos dizer que M corre no espaço f(n).

Estimamos a complexidade espacial da máquina de Turing usando notação assintótica.

Seja $ f \ colon N \ rightarrow R ^ + $ uma função. As classes de complexidade do espaço podem ser definidas da seguinte forma -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE é a classe de linguagens que podem ser decididas no espaço polinomial em uma máquina de Turing determinística.

Em outras palavras, PSPACE = U_k SPACE (n^k)

Teorema de Savitch

Um dos primeiros teoremas relacionados à complexidade do espaço é o teorema de Savitch. De acordo com este teorema, uma máquina determinística pode simular máquinas não determinísticas usando uma pequena quantidade de espaço.

Para a complexidade do tempo, tal simulação parece exigir um aumento exponencial no tempo. Para a complexidade do espaço, este teorema mostra que qualquer máquina de Turing não determinística que usaf(n) espaço pode ser convertido em uma TM determinística que usa f²(n) espaço.

Portanto, o teorema de Savitch afirma que, para qualquer função, $ f \ colon N \ rightarrow R ^ + $, onde $ f (n) \ geqslant n $

NSPACE(f(n)) ⊆ SPACE(f(n))