La complejidad espacial de un algoritmo o estructura de datos es la cantidad máxima de espacio utilizada en cualquier momento, ignorando el espacio utilizado por la entrada al algoritmo. La notación para la complejidad del espacio es exactamente la misma que la notación para la complejidad del tiempo.
Ejemplos:
La búsqueda binaria usa [math] \ Theta (1) [/ math] space *. El único espacio adicional utilizado es el número constante de índices.
- ¿Hay alguna evidencia de organismos que evolucionaron para tener un cerebro computacional en serie (como un procesador de computadora), en lugar del cerebro computacional paralelo (red neuronal)?
- ¿Los desarrolladores de aplicaciones CRUD serán reemplazados por AI?
- ¿Dónde puedo encontrar las tareas y otros recursos adicionales para Harvard CS51?
- ¿Vale la pena obtener un certificado verificado de CS50 en edX?
- ¿Qué porcentaje de miembros de la facultad en su departamento de CS se ocupan del aprendizaje automático?
La ordenación rápida usa [math] \ Theta (1) [/ math] space * si se realiza en el lugar (donde se modifica la matriz de entrada), pero tiene la complejidad de espacio [math] \ Theta (n) [/ math] de lo contrario (ya que debe construir una nueva lista de tamaño [math] n [/ math]).
El almacenamiento de un gráfico en forma de lista de adyacencia requiere espacio [matemático] \ Theta (V + E) [/ matemático] *. Para cada vértice, almacenamos una lista de sus bordes. Hay bordes [matemáticos] E [/ matemáticos], por lo que claramente usamos el espacio [matemático] \ Omega (E) [/ matemático]. Sin embargo, también necesitamos almacenar referencias [matemáticas] \ Omega (V) [/ matemáticas] en las listas.
El almacenamiento de un gráfico en forma de matriz requiere espacio [matemático] \ Theta (V ^ 2) [/ matemático]. Para cada par de vértices usamos el espacio [math] \ Theta (1) [/ math] para indicar si el borde entre ellos está presente o no.
* Esto realmente depende del modelo que especifique. En un modelo más formal, cualquier índice o puntero en una estructura de tamaño [math] n [/ math] requiere [math] \ Omega (\ log n) [/ math] bits, por lo que la complejidad del espacio será [math] \ Omega (\ log n) [/ math]. Por lo general, se utiliza un modelo más simple en el que se considera que los índices y los punteros toman espacio [matemática] \ Theta (1) [/ matemática].
También se hacen los mismos tipos de simplificaciones cuando se considera la complejidad del tiempo. Por lo general, se supone que agregar dos números es una operación [matemática] \ Theta (1) [/ matemática], pero agregar dos números de bit [matemática] n [/ matemática] necesariamente requiere [matemática] \ Omega (n) [/ matemática] hora.
