No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Complejidad espacial

5/18
Recursos

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: 鈥淰isi贸n鈥 y 鈥淣ova鈥. 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.

Ejemplo de espacio necesario para dos algoritmos diferentes

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.

complejidad_algoritmica06.png

Contribuci贸n creada por Andr茅s Guano (Platzi Contributor).

Aportes 10

Preguntas 0

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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.

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

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 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

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.

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.

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. Es decir, no nos importa si el algoritmo realiza su trabajo utilizando 10KB o 3GB, sino cu谩nto m谩s consume cuando hay diez datos en la entrada comparado con cu谩nto consume con dos datos en la entrada.

Complejidad spacial, este estudia los algoritmo que ocupan poco espacio

La complejidad espacial: