Complejidad espacial
Clase 5 de 18 • Curso de Complejidad Algorítmica con JavaScript
Resumen
La complejidad espacial es la cantidad de espacio en memoria que un algoritmo emplea al ejecutarse. En otras palabras, cómo el algoritmo ocupa espacio en memoria con la cantidad de elementos de entrada que debe procesar.
Comparación de algoritmos
Comparemos dos algoritmos que resuelven el mismo problema: “Visión” y “Nova”. El primer algoritmo aumenta su espacio mientras más estudiantes sean ingresados. Mientras que el segundo algoritmo aumenta exponencialmente su espacio necesario.
Aunque ambos algoritmos resuelven el mismo problema, manejan la cantidad de memoria utilizada de manera diferente a medida que procesa más elementos.
Espacio auxiliar en la complejidad espacial
La complejidad espacial incluye el espacio auxiliar y el espacio ocupado por los datos de entrada. En el espacio auxiliar están todos los procesos que procesa el espacio de entrada.
El espacio de entrada no es importante. ¿Por qué? Porque al comparar los algoritmos, el espacio de entrada es el mismo para todos los casos, por lo que el espacio auxiliar es el que los diferencia y el necesario para evaluar el algoritmo.
Contribución creada por Andrés Guano (Platzi Contributor).