DAA - Space Complexities

In questo capitolo, discuteremo la complessità dei problemi computazionali rispetto alla quantità di spazio richiesta da un algoritmo.

La complessità dello spazio condivide molte delle caratteristiche della complessità del tempo e serve come un ulteriore modo per classificare i problemi in base alle loro difficoltà computazionali.

Cos'è la complessità spaziale?

La complessità dello spazio è una funzione che descrive la quantità di memoria (spazio) che un algoritmo richiede in termini di quantità di input per l'algoritmo.

Si parla spesso di extra memorynecessario, senza contare la memoria necessaria per memorizzare l'input stesso. Ancora una volta, usiamo unità naturali (ma di lunghezza fissa) per misurarlo.

Possiamo usare i byte, ma è più facile usare, diciamo, il numero di interi usati, il numero di strutture di dimensioni fisse, ecc.

Alla fine, la funzione che creeremo sarà indipendente dal numero effettivo di byte necessari per rappresentare l'unità.

La complessità dello spazio a volte viene ignorata perché lo spazio utilizzato è minimo e / o ovvio, tuttavia a volte diventa una questione importante quanto la complessità del tempo

Definizione

Permettere M essere deterministico Turing machine (TM)che si ferma su tutti gli input. La complessità spaziale diM è la funzione $ f \ due punti N \ rightarrow N $, dove f(n) è il numero massimo di celle del nastro e M esegue la scansione di qualsiasi input di lunghezza M. Se la complessità dello spazio diM è f(n), possiamo dirlo M corre nello spazio f(n).

Stimiamo la complessità spaziale della macchina di Turing utilizzando la notazione asintotica.

Sia $ f \ due punti N \ freccia destra R ^ + $ una funzione. Le classi di complessità spaziale possono essere definite come segue:

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 è la classe di linguaggi decidibili nello spazio polinomiale su una macchina di Turing deterministica.

In altre parole, PSPACE = U_k SPACE (n^k)

Teorema di Savitch

Uno dei primi teoremi relativi alla complessità spaziale è il teorema di Savitch. Secondo questo teorema, una macchina deterministica può simulare macchine non deterministiche utilizzando una piccola quantità di spazio.

Per la complessità temporale, una simile simulazione sembra richiedere un aumento esponenziale del tempo. Per la complessità spaziale, questo teorema mostra che qualsiasi macchina di Turing non deterministica che utilizzaf(n) lo spazio può essere convertito in una TM deterministica che utilizza f²(n) spazio.

Quindi, il teorema di Savitch afferma che, per qualsiasi funzione, $ f \ due punti N \ freccia destra R ^ + $, dove $ f (n) \ geqslant n $

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

Relazione tra classi di complessità

Il diagramma seguente illustra la relazione tra le diverse classi di complessità.

Fino ad ora, non abbiamo discusso delle classi P e NP in questo tutorial. Questi saranno discussi in seguito.