No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Complejidad espacial

7/18
Recursos

Aportes 7

Preguntas 0

Ordenar por:

Los aportes, preguntas y respuestas son vitales para aprender en comunidad. Regístrate o inicia sesión para participar.

La complejidad espacial, se encarga de calcular cuanto espacio en memoria puede ocupar un algoritmo, a parte del espacio ocupado por los datos de entrada, existe el espacio auxiliar, el cual es el espacio creado por el mismo algoritmo para hacer otro procesos, por ejemplo: filtrar un array, hacer un sort de números, etc. El espacio auxiliar incluso puede llegar a hacer mucho más grande que el espacio de los datos de entrada, y está relacionado al algoritmo mas que a los datos recibos.

Memoria

Cuando trabajamos con grandes cantidades de datos tendremos que almacenar información en otras partes.

Espacio auxiliar

La complejidad espacial incluye el espacio auxiliar y el espacio ocupado por los datos de entrada.

El espacio auxiliar es el espacio total - espacio datos de entrada

Los pasos realizados dentro del algoritmo, pueden ser operaciones que creen más espacio (como crear una lista donde ir dejando los resultados de un algoritmo de ordenamiento).

El espacio auxiliar es más importante que los datos de entrada.

🌌 Complejidad espacial

Apuntes

  • Necesitamos un algoritmo, que ocupe poco espacio. Esta situación se nos puede dar cuando trabajamos con grandes cantidades de datos los cuales tendremos que almacenar información en otras partes
  • La complejidad espacial se separa en dos partes
    1. Espacio ocupado por datos de entrada
    2. Espacio auxiliar ⇒ (espacio total - espacio por los datos de entrada)
  • Muchas veces existen algoritmos que ocupan mucho espacio (ejm. Creando muchas estructuras de datos)
  • El espacio auxiliar es más importante que el espacio de datos de entrada debido a que estos no cambian su tamaño
📌 **RESUMEN:**  La complejidad espacial trata de medir el espacio que ocupa un algoritmo dividiendo tanto en espacio por los datos de entrada y el espacio auxiliar el cual es el espacio total ocupado por el algoritmo menos el espacio de los datos de entrada

Fijate en el codigo de abajo

function plusOne(arr){
    const result = arr.map(item => item + 1)
    return result;
}

Cuando nos referimos a Espacio Auxiliar, estamos hablando del espacio usado dentro del proceso. En el caso de arriba, se esta creando un nuevo array al momento de usar map, ya que este método es inmutable, lo que crea un array nuevo, en lugar de modificar el pasado como parámetro. Este nuevo array que se ha creado es lo que debemos tomar en cuenta para hacer nuestro análisis Espacial

Complejidad espacial

Ejemplo buscando un algoritmo que ocupe poco espacio Teniendo multiples algoritmos:

El algoritmo Vision realiza la operación

Con 10 datos la realiza ocupando 10 Kilobytes
Con 20 datos la realiza ocupando 20 Kilobytes
Con 30 datos la realiza ocupando 30 Kilobytes

El algoritmo Nova realiza la operación

Con 10 datos la realiza ocupando 10 Kilobytes
Con 20 datos la realiza ocupando 100 Kilobytes
Con 30 datos la realiza ocupando 1000 Kilobytes

Memoria

cuando trabajamos con grandes cantidades de datos tendremos que almacenar información en otras partes

Espacio auxiliar

La complejidad espacial el espacio auxiliar y el espacio ocupado por los datos de entrada

es más importante que el espacio de entrada, ya que el espacio auxiliar es generado por las operaciones internas que realice nuestro algoritmo. Todos los algoritmos ocupan el mismo tamaño en su entrada, pero el espacio auxiliar varía según que lógica apliquemos en el algoritmo.

Por ejemplo, el espacio auxiliar Puede ser generado por algoritmos de ordenamiento al crear nuevas variables. O las técnicas que usemos para resolver el problema, las creaciones de listas y diccionarios en el algoritmo aumentan el espacio auxiliar utilizado por el algoritmo.

Complejidad espacial

La complejidad espacial no es una medida de cuánta memoria utiliza un algoritmo al ejecutarse sino de cómo varía dicho consumo cuando existe una variación en la cantidad de datos de entrada. La complejidad espacial no tiene unidad, es una medida relativa.

Memoria: Cuando trabajamos con grandes cantidades de datos tendremos que almacenar información en otras partes.

Espacio auxiliar: La complejidad espacial incluye el espacio auxiliar y el espacio ocupado por los datos de entrada. El espacio auxiliar es más importante que el espacio de datos de entrada, ya que dependiendo del algoritmo se pueden llegar a crear copias de los datos de entrada, ya sea para ordenarlos, o para cualquier objetivo, y esto puede llegar a ocupar mucho espacio mientras más datos se procesen.

Gestión de memoria en JavaScript

Sin importar el lenguaje de programación, el ciclo de memoria es casi siempre parecido al siguiente:

  1. Reservar la memoria necesaria.
  2. Utilizarla (lectura, escritura).
  3. Liberar la memoria una vez ya no es necesaria.

Complejidad spacial, este estudia los algoritmo que ocupan poco espacio