Complejidad espacial

La complejidad espacial de un algoritmo o un programa de computadora es la cantidad de espacio de memoria requerida para resolver una instancia del problema computacional en función de las características de la entrada. Es la memoria que requiere un algoritmo hasta que se ejecuta por completo. ^[1]

Similar a la complejidad del tiempo , la complejidad del espacio a menudo se expresa asintóticamente en notación O grande , como etc., donde $n$ es una característica de la entrada que influye en la complejidad del espacio. ${\ Displaystyle O (n),}$ ${\ Displaystyle O (n \ log n),}$ ${\ Displaystyle O (n ^ {\ alpha}),}$ ${\ Displaystyle O (2 ^ {n}),}$

De manera análoga a las clases de complejidad temporal DTIME (f (n)) y NTIME (f (n)) , las clases de complejidad DSPACE (f (n)) y NSPACE (f (n)) son los conjuntos de lenguajes que se pueden decidir mediante deterministas ( respectivamente, no deterministas) máquinas de Turing que utilizan el espacio. Las clases de complejidad PSPACE y NPSPACE permiten ser cualquier polinomio, análogamente a P y NP . Es decir, ${\ Displaystyle O (f (n))}$ ${\ Displaystyle f}$

El teorema de la jerarquía espacial establece que, para todas las funciones construibles en el espacio , existe un problema que puede ser resuelto por una máquina con espacio de memoria, pero no puede ser resuelto por una máquina con espacio asintóticamente menor que el espacio. ${\ Displaystyle f (n)}$ ${\ Displaystyle f (n)}$ ${\ Displaystyle f (n)}$

Además, el teorema de Savitch da la contención inversa de que si , ${\ Displaystyle f \ in \ Omega (\ log (n))}$

Como corolario directo ,. Este resultado es sorprendente porque sugiere que el no determinismo puede reducir el espacio necesario para resolver un problema solo en una pequeña cantidad. En contraste, la hipótesis del tiempo exponencial conjetura que para la complejidad del tiempo, puede haber una brecha exponencial entre la complejidad determinista y no determinista. ${\ Displaystyle {\ mathsf {PSPACE}} = {\ mathsf {NPSPACE}}}$