DAA - Complejidades espaciales

En este capítulo, discutiremos la complejidad de los problemas computacionales con respecto a la cantidad de espacio que requiere un algoritmo.

La complejidad espacial comparte muchas de las características de la complejidad temporal y sirve como una forma más de clasificar los problemas de acuerdo con sus dificultades computacionales.

¿Qué es la complejidad espacial?

La complejidad del espacio es una función que describe la cantidad de memoria (espacio) que toma un algoritmo en términos de la cantidad de entrada al algoritmo.

A menudo hablamos de extra memorynecesario, sin contar la memoria necesaria para almacenar la entrada en sí. Nuevamente, usamos unidades naturales (pero de longitud fija) para medir esto.

Podemos usar bytes, pero es más fácil usar, digamos, el número de enteros usados, el número de estructuras de tamaño fijo, etc.

Al final, la función que se nos ocurra será independiente del número real de bytes necesarios para representar la unidad.

La complejidad del espacio a veces se ignora porque el espacio utilizado es mínimo y / o obvio, sin embargo, a veces se convierte en un tema tan importante como la complejidad del tiempo.

Definición

Dejar M ser un determinista Turing machine (TM)que se detiene en todas las entradas. La complejidad espacial deM es la función $ f \ colon N \ rightarrow N $, donde f(n) es el número máximo de celdas de cinta y M escanea cualquier entrada de longitud M. Si la complejidad espacial deM es f(n), podemos decir eso M corre en el espacio f(n).

Estimamos la complejidad espacial de la máquina de Turing usando notación asintótica.

Sea $ f \ colon N \ rightarrow R ^ + $ una función. Las clases de complejidad espacial se pueden definir de la siguiente manera:

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 es la clase de lenguajes que se pueden decidir en un espacio polinomial en una máquina de Turing determinista.

En otras palabras, PSPACE = Uk SPACE (nk)

Teorema de Savitch

Uno de los primeros teoremas relacionados con la complejidad del espacio es el teorema de Savitch. Según este teorema, una máquina determinista puede simular máquinas no deterministas utilizando una pequeña cantidad de espacio.

Para la complejidad del tiempo, tal simulación parece requerir un aumento exponencial en el tiempo. Para la complejidad del espacio, este teorema muestra que cualquier máquina de Turing no determinista que utilicef(n) el espacio se puede convertir en una TM determinista que utiliza f2(n) espacio.

Por tanto, el teorema de Savitch establece que, para cualquier función, $ f \ colon N \ rightarrow R ^ + $, donde $ f (n) \ geqslant n $

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

Relación entre clases de complejidad

El siguiente diagrama muestra la relación entre diferentes clases de complejidad.

Hasta ahora, no hemos discutido las clases P y NP en este tutorial. Estos se discutirán más adelante.