Complejidad espacial en práctica

Clase 8 de 18 • Curso de Complejidad Algorítmica con JavaScript

Contenido del curso

Fundamentos de Algoritmos

Complejidad algorítmica

Análisis asintótico

Recomendaciones

Bonus

18
Complejidad de algoritmos en búsqueda de payloads de SpaceX
04:03 min

Tomar examen

Resumen

La complejidad espacial es diferente a la complejidad temporal. Los diferentes compiladores asignan un espacio distinto de memoria para almacenar variables.

La diversidad de tamaños y formas con las que el compilador almacena información es interesante, pero para el propósito que tenemos, podemos simplificarlo a contar cuántas variables se definen para almacenar arreglos, números o cadenas.

Ejemplos de complejidad espacial

El algoritmo contar recibe como parámetro un número y cuenta hasta ese número. ¿Qué se genera en el algoritmo? Una variable i que almacena un número.

function contar(n) {
    for (let i = 0; i< n; i++){
        console.log(i)
    }
}

El algoritmo repetirArreglo recibe como parámetro un array y lo duplica, por ende, está generando un espacio en memoria similar al array inicial.

function repertirArreglo (array) {
    let arregloRepetido = [...array]
    return arregloRepetido
}

El algoritmo convertirAString recibe como parámetro un array de números, y por cada número lo convierte a string. De esta manera, se está generando un valor en memoria diferente, ya que los compiladores manejan los números y las palabras de diferente manera.

function convertirAString  (array) {
    let resultado = array.map(el => el.toString())
    return resultado
}

El algoritmo generarMatriz recibe un valor numérico como parámetro para generar una array de arrays o una matriz. En consecuencia, se está generando un número de elementos igual al cuadrado del parámetro y una cantidad de arrays igual al valor del parámetro.

function generarMatriz (valor){
    let matriz = new Array(valor)
    for (let i = 0; i < valor; i++){
        matriz[i] = new Array(valor).fill(0)
    }
    return matriz
}

console.log( generarMatriz(5))
/* 
[
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0 ]
]*/

A partir de un valor numérico igual a 25, se generaron 25 elementos de la matriz y 5 arrays individuales en memoria.

Contribución creada por Marcelo Arias y Andrés Guano (Platzi Contributor).

Comentarios

Irving Juárez

student•

Creo que hay un detalle en el código mostrado en esta clase. Ya que en la función repetir, lo que hacemos es crear una nueva variable que es igual a el array que se le paso como parámetro. Básicamente esto:

function repetir(arr){
  let newArray = arr;
  return newArray;
}

Sin embargo, creo que en este caso newArray solo estaría apuntando al espacio en memoria de arr, por lo que aquí no se estaría realmente haciendo otro array. . Creo que JS hace esto con funciones y con arrays. En casos donde hay arrays anidados, tendríamos que aplicar una funciona recursiva, aplicando DeepCopy para poder hacer un arreglo u objeto nueva, pero en este caso, creo que para realmente crear un nuevo array, podemos aplicar el spread operator:

function repetir(arr){
  const newArray = [...arr]
  return newArray;
}

Karen Benites Segura

student•

Estaba buscando este comentario, y estás en lo correcto. Para hacer una copia de un array se puede usar el spread operator, con Array.from o con slice. Pero asignar la "variable" original del un array a otra variable no crea una copia del array. Sólo se está haciendo que dos variables diferentes apunten al mismo espacio en memoria RAM del array en sí

Marcelo Arias

teacher•

¿Cómo medimos un recurso?

⌚ En Complejidad Temporal podemos usar funciones como y para medir el tiempo en que se ejecuta un algoritmo.
🌌 En Complejidad Espacial es diferente. Cada compilador asigna un espacio distinto de memoria para almacenar números o palabras.

📦 La diversidad de tamaños y formas con las que el compilador almacena información es interesante, pero para el propósito que tenemos, podemos simplificarlo a contar cuántas variables se definen para almacenar arreglos, números o cadenas.

Brandon Argel Verdeja Domínguez

student•

Práctica Complejidad Espacial

Cada compilador asigna un espacio distinto de memoria para almacenar números o palabras.

La diversidad de tamaños y formas con las que el compilador almacena información es interesante, pero para el propósito que tenemos, podemos simplificarlo a contar cuántas variables se definen para almacenar arreglos, números o cadenas.

Luis Rogelio Reyes Hernandez

student•

En la complejidad Espacial vamos contando las variables que se van creando y que tipos de variables son las que se están creando.

Yago Aguero

student•

Buenas! en versión app, cada vez que abro unas lección se abre primero la configuración de segundo plano. Es muy recurrente, seria genial si pudieran solucionarlo. gracias!!!

Ramses Acosta

student•

¿Qué herramienta se puede usar para tener métricas de complejidad espacial?

Jorge Marroquin

student•

Estas 3 herramientas pueden ayudarte a medir la complejidad espacial de un programa en JavaScript:

Plato: Es una herramienta de análisis de código que genera informes de complejidad ciclomática y complejidad de Halstead para archivos JavaScript.
EsLint: Es una herramienta de análisis de código estático que puede ser configurada para detectar patrones específicos de código, incluyendo patrones de complejidad espacial.
CodeClimate: Es una plataforma de análisis de código que puede ser configurada para analizar la complejidad espacial y temporal de un programa en JavaScript. Ofrece recomendaciones de refactorización para reducir la complejidad.

Leonardo Buezo

student•

Código de la clase con un par de ejemplos para correr en la terminal de comandos:

function counter(length) {
    for(let i = 0; i < length; i++) {
        console.log(i);
    }
}

function arrayConverter(arr) {
    return arr.map( el => el.toString());
}

function array2DConverter(value) {
    let newArr2D = new Array(value);
    for(let i = 0; i < value; i++) {
        newArr2D[i] = new Array(value).fill(value);
    }
    return newArr2D;
}

// See through console.log the auxiliar space used by arrayConverter(value) function
console.log(arrayConverter([2, 3, 4]));

// See how a big auxiliar space afects the time performance
let start = performance.now();
console.log(array2DConverter(20000));
let elapsed = (performance.now() - start);
console.log("Elapsed Time: " + elapsed.toFixed(2) + " miliseconds");

Lo que se puede ver en el ejemplo del array2DConverter(20000) es cómo se ve afectada también la performance en tiempo además de espacio, es decir se incrementa notoriamente la complejidad espacio tiempo (o como se llame). En mi laptop el resultado fue de 6.5 segundos promedio.

Anfernee Valera

student•

Has estado geniales las clases c:

Jose Rafael Oliva Montes

student•

Gracias

function counter(length) {
    for(let i = 0; i < length; i++) {
        console.log(i);
    }
}

function arrayConverter(arr) {
    return arr.map( el => el.toString());
}

function array2DConverter(value) {
    let newArr2D = new Array(value);
    for(let i = 0; i < value; i++) {
        newArr2D[i] = new Array(value).fill(value);
    }
    return newArr2D;
}

// See through console.log the auxiliar space used by arrayConverter(value) function
console.log(arrayConverter([2, 3, 4]));

// See how a big auxiliar space afects the time performance
let start = performance.now();
console.log(array2DConverter(20000));
let elapsed = (performance.now() - start);
console.log("Elapsed Time: " + elapsed.toFixed(2) + " miliseconds");

Complejidad espacial en práctica

Fundamentos de Algoritmos

Complejidad Algorítmica con JavaScript: Eficiencia y Selección

Conceptos Fundamentales de Algoritmos en Programación

Optimización de Algoritmos: Tiempo y Espacio en JavaScript

Complejidad algorítmica

Teoría de la Complejidad: Tiempo y Espacio en Algoritmos