Complejidad de algoritmos en búsqueda de payloads de SpaceX

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

💭 Hasta ahora hemos visto algoritmos que realizan tareas como buscar índices u ordenar elementos. Sin embargo, JavaScript ya cuenta con funciones nativas para esos propósitos.

🤔 Entonces, ¿Qué tal si determinamos la complejidad de un algoritmo más avanzado? Un algoritmo que no esté incorporado en JavaScript, que reciba datos de una API y que tenga una estructura compleja.

🚀 Verificando un payload de SpaceX

Entonces, imagina que tú con tus amigos/as están en un reto donde desarrollan algoritmos capaces de verificar si existe un payload (una carga útil) dentro de una lista de los lanzamientos de SpaceX.

En otras palabras, este algoritmo debe recibir la lista de lanzamientos, más el ID del payload, y te devolverá true o false dependiendo si existe o no.

Cada uno de ustedes desarrolla un algoritmo diferente: Alfa, Beta y Delta, todos trabajan sobre la misma API y funcionan súper bien.

Sin embargo, cada mes se hacen muchos más lanzamientos, con más payloads, lo que significa que los datos que extraeremos de esta API empezarán a crecer. Si antes teníamos 70 payloads, el siguiente mes podríamos tener 120, y luego 200, y así.

Por ello buscamos ese algoritmo que gestione mejor el tiempo de búsqueda. 🔍

⌚ ¿Puedes encontrar cuál es? 💻

Datos importantes

Si deseas probar los algoritmos, aquí está la API que debes declarar:

const SPACEX_API = 'https://api.spacexdata.com/v3/launches';

Pero recuerda que en el estudio de la complejidad temporal solo hacemos un análisis de línea por línea del código...

Y si deseas probar los algoritmos:

algoritmoBeta('FalconSAT-2', SPACEX_API); // true
algoritmoBeta('FalconSAT-3', SPACEX_API); // false

Estos son los algoritmos a evaluar:

Algoritmo Alfa

async function algoritmoAlfa(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    for (let i = 0; i < data.length; i++) {
        let payloads = data[i].rocket.second_stage['payloads'];
        for (let j = 0; j < payloads.length; j++) {
            if (payloadId == payloads[j].payload_id) {
                return true;
            }
        }
    }
    return false;
}

Algoritmo Beta

async function algoritmoBeta(payloadId, payloadAPI) {
    let arreglosCoinciden = (arreglo1, arreglo2) => {
        if (arreglo1.length != arreglo2.length) {
            return false;
        }
        for (let i = 0; i < arreglo1.length; i++) {
            if (arreglo1[i] != arreglo2[i]) {
                return false;
            }
        }
        return true;
    };
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    let payloadIdArray = payloadId.split('');
    for (let i = 0; i < data.length; i++) {
        let payloads = data[i].rocket.second_stage.payloads;
        for (let j = 0; j < payloads.length; j++) {
            if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) {
                return true;
            }
        }
    }
    return false;
}

Algoritmo Delta

async function algoritmoDelta(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    let listaDePayloads = [];
    let longitudData = data.length;

    for (let i = 0; i < longitudData; i++) {
        let payloads = data[i].rocket;
        listaDePayloads.push(...payloads.second_stage['payloads']);
    }

    for (let i = 0; i < listaDePayloads.length; i++) {
        let localPayloadId = listaDePayloads[i].payload_id;
        if (localPayloadId == payloadId) {
            return true;
        } else {
            return false;
        }
    }
}

Observaciones

❓ Interesante. Tenemos muchos ciclos for. ¿Es eso un problema?

¡Genial! Has notado que tenemos ciclos for recorriendo la lista de payloads, esto implica que la lista de payloads (representada con payloadsAPI) tiene más participación en todo el algoritmo que el otro parámetro payloadId. Por lo tanto, enfócate en qué estructuras usa payloadsAPI.

❓ Usamos async/await porque estamos manejando APIs, y APIs toman un tiempo X en cargar los datos. ¿Esto es más complejidad temporal?

Sí. Utilizar una API es la forma más común en la que el tiempo se escapa de nuestras manos (dada la estructura de JavaScript), y por ello usamos async/await. Siempre cuéntalas en tu análisis.

Marcelo Arias

teacher•

💚 Muchos de los algoritmos que hemos visto en el curso son del tipo matemático u ordenamiento/búsqueda. 🚀 Aquí te dejo un algoritmo un poco más robusto. Puedes realizarlo antes o después del examen. ⚔ ¡Las reglas de la complejidad ya las tienes!

Carlos Delgado

student•

El Algoritmo Alfa tiene una complejidad temporal simplificada de O(n^2) porque tiene un ciclo for dentro de otro for.
El Algoritmo Beta tiene una complejidad temporal de O (n^3)
El Algoritmo Delta es el más eficiente temporalmente ya que a pesar de tener 2 for, estos no están anidados por lo que al calcular su complejidad estas O(n) se suman O(n) + O(n) dando como resultado O(n)

Angel Solis

student•

Creo que estas equivocado cmpañero. El algotirmo beta tiene un big O(n^2), ya que es n^2 + n. Si el primer for estuviera anidado en el tercer for, sí sería n^3

Leonardo Buezo

student•

Angrub, una aclaración: arreglosCoinciden es una function expression la cual es llamada en la validación que hace el IF del segundo FOR anidado. Esto incrementa la complejidad temporal. Saludos!

Lautaro Els

student•

De los 3 el delta es el mas eficiente de todos

ALFA

/**
 * Complejidad Temporal -> O( n^2)
 */


async function algoritmoAlfa(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    for (let i = 0; i < data.length; i++) { //O(n^2)
        let payloads = data[i].rocket.second_stage['payloads']; //O(1)
        for (let j = 0; j < payloads.length; j++) {  //(n)
            if (payloadId == payloads[j].payload_id) { //O(1)
                return true;
            }
        }
    }
    return false;
}

BETA

/**
 * Complejidad Temporal -> O( n^2  )
 
 */

async function algoritmoBeta(payloadId, payloadAPI) {
    let arreglosCoinciden = (arreglo1, arreglo2) => { //O(1)
        if (arreglo1.length != arreglo2.length) { //O(1)
            return false;
        }
        for (let i = 0; i < arreglo1.length; i++) { //O(n)
            if (arreglo1[i] != arreglo2[i]) {
                return false;
            }
        }
        return true;
    };
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    let payloadIdArray = payloadId.split(''); //O(1)
    for (let i = 0; i < data.length; i++) { //O(n^2)
        let payloads = data[i].rocket.second_stage.payloads; //O(1)
        for (let j = 0; j < payloads.length; j++) { //(n)
            if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) { //O(1)
                return true;
            }
        }
    }
    return false;
}

DELTA

/**
 * Complejidad Temporal -> O( n )
 */


async function algoritmoDelta(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    let listaDePayloads = []; //O(1)
    let longitudData = data.length; //O(1)

    for (let i = 0; i < longitudData; i++) { //O(n)
        let payloads = data[i].rocket; //O(1)
        listaDePayloads.push(...payloads.second_stage['payloads']);
    }

    for (let i = 0; i < listaDePayloads.length; i++) { //O(n)
        let localPayloadId = listaDePayloads[i].payload_id; //O(1)
        if (localPayloadId == payloadId) { //O(1)
            return true;
        } else {
            return false;
        }
    }
}

Christian Boffill

student•

Los métodos de arrays en JS como map, filter, sort, reduce, findIndex, etc. ¿Cómo es que les puedo dar su notación correctamente??? ¿Tendría que saber como están construidos o hay una forma de analizarlos??? gracias

Marcelo Arias

teacher•

¡Hola Christian! Muy buenas preguntas.

Primero, si los arreglos tienen relación directa con el input (la entrada) entonces sí es necesario analizarlos para obtener la notación Big-O:

// .map() recibe a un input ✅
const algoritmoA = (n) => {
  n.map((item) => console.log(item)); // <- Necesitamos analizarlo
};

algoritmoA([1, 2, 3, 4, 5]);

// .map() no recibe al input ❌
const algoritmoB = (n) => {
  ['x', 'y'].map((item) => console.log(item));
};

algoritmoB([1, 2, 3, 4, 5]);

Y en el caso en que necesitemos analizarlos → Necesitamos entender su estructura, y determinar si al momento de incrementar el tamaño de la entrada, el método tendrá que incrementarse igual.

Me dejaste unos ejemplos muy buenos:

.map: Recorre un arreglo como for, entonces es un O(n).
.filter: Recorre un arreglo como for y filtra los elementos necesarios, entonces es un O(n).
.reduce: Recorre un arreglo como for y transforma los elementos, entonces es un O(n).
.findIndex: Recorre un arreglo como for hasta encontrar el índice de un elemento, entonces es un O(n).

Sin embargo, sí existen casos donde tenemos que saber cómo están construidos los algoritmos según el entorno de ejecución. Para un método como sort, tenemos muchos algoritmos de ordenamiento, y los entornos de ejecución no usan los mismos.

Por ejemplo:

Chrome usa TimSort que es O(n)
Firefox usa Merge Sort que es O(n * log(n))

🤔 En este caso ¿Qué notación utilizaríamos? Big-O se alinea al peor caso posible (el de la complejidad mayor). Como respuesta podemos decir que O(n * log(n)), pues es mayor a O(n).

¿Y si estamos interesados en un navegador o entorno de ejecución en específico?

✅ Gracias a que Big-O es un estándar, lo usual es encontrar esta medida en la documentación del navegador o del entorno de ejecución, o bien encontrar el nombre del algoritmo utilizado. (Por ejemplo, si es Merge Sort sabemos que es O(n * log(n))).

Daniel Omar Hernández Muñoz

student•

Simplificandolo Alfa = Big O (n^2) Beta = Big O (n^3) Delta = Big O (n) Nota: Me queda un poco en duda como se le puede tomar a funciones como .map() .split() etc.

Marco Antonio Miranda Sandoval

student•

Hola Daniel! Comparando tus resultados con los míos, veo que hemos llegado a la misma conclusión. Y al igual que tú, tengo la misma duda en cuanto a los métodos que mencionas tú, bueno, en todos en general. Has intentando buscar en la Doc de MDN? Saludos

Diego Reyes Cabrera

student•

Pienso que todos o la gran mayoría de los métodos de Arrays tienen una complejidad O(n) dada la misma naturaleza de la estructura de una lista. La mayoría de los métodos, incluyendo .map y .split, recorren cada elemento de forma lineal.

Anfernee Valera

student•

Creo que en el algoritmo alfa quedaría asi:

/* 
    Complejidad Temporal -> O( n² ) ya que tiene un ciclo for anidado.
    Complejidad Temporal -> O( n² ) Por la data multinivel que se consigue al procesar la solicitud de la API
    Espacio auxiliar -> O( n² ) El espació auxiliar es este, ya que los valores de entrada son solamente dos pares de String, el procesamiento de esa data está dentro de la función (n² - 2 ) -> (n²)
*/

Luis Rogelio Reyes Hernandez

student•

Mis solución y análisis del reto

/**
 * Complejidad temporal => O(n+n + n * (1 + n * (1 + 1)) + 1) = O(2n + n^2) = O(n^2)
 *
 * Complejidad Espacial => O( 1 + 1 + x^2 + x + 1 + x + 1) = O(x^2)
 * Espacio Auxiliar => O(x^2)
 *
 * @param {*} payloadId
 * @param {*} payloadAPI
 * @returns
 */
export default async function algoritmoAlfa(payloadId, payloadAPI) { // Espacial O(1), O(1)
  // temporal O(n) metodo async su tiempo es indeterminado
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI); // entrada de datos?

  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();

  // Temporal O(n)
  // Espacial O(1)
  for (let i = 0; i < data.length; i++) {
    // Temporal O(1)
    // Espacial O(x)
    let payloads = data[i].rocket.second_stage['payloads'];

    // Temporal O(n)
    // Espacial O(1)
    for (let j = 0; j < payloads.length; j++) {
      // Temporal O(1)
      if (payloadId == payloads[j].payload_id) {
        // Temporal O(1)
        return true;
      }
    }
  }
  // Temporal O(1)
  return false;
}

/**
 * Complejidad temporal => O(n^3)
 * Complejidad espacial => O(n^2)
 * Espacio auxiliar => O(n^2)
 * @param {*} payloadId 
 * @param {*} payloadAPI 
 * @returns 
 */
export default async function algoritmoBeta(payloadId, payloadAPI) { // Espacial O(1), O(1)

  // Temporal O(1)
  // Espacial O(1)
  let arreglosCoinciden = (arreglo1, arreglo2) => {
    // Temporal O(1)
    if (arreglo1.length != arreglo2.length) {
      // Temporal O(1)
      return false;
    }
    // Temporal O(n)
    // Espacial O(1)
    for (let i = 0; i < arreglo1.length; i++) {
      // Temporal O(1)
      if (arreglo1[i] != arreglo2[i]) {
        // Temporal O(1)
        return false;
      }
    }
    // Temporal O(1)
    return true;
  };

  // Temporal O(n)
  // Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI);// entrada de datos?

  // Temporal O(n)
  // Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();

  // Temporal O(1)
  // Espacial O(1)
  let payloadIdArray = payloadId.split('');

  // Temporal O(n)
  // Espacial O(1)
  for (let i = 0; i < data.length; i++) {
    // Espacial O(1)
    let payloads = data[i].rocket.second_stage.payloads;
    // Temporal O(n)
    // Espacial O(1)
    for (let j = 0; j < payloads.length; j++) {
      // Temporal O(n) el metodo arreglosCoinciden es temporal O(n)
      if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) {
        // Temporal O(1)
        return true;
      }
    }
  }
  // Temporal O(1)
  return false;
}

/**
 * Complejidad temporal => O(n + n + n + n) = O(n)
 * Complejidad Espacial => O(x^2)
 * Espacio auxiliar => O(x^2)
 * @param {*} payloadId 
 * @param {*} payloadAPI 
 * @returns 
 */
export default async function algoritmoDelta(payloadId, payloadAPI) { // Espacial O(1), O(1)

  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI); // entrada de datos?
  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();
  // temporal O(1)
  // espacial O(1)
  let listaDePayloads = [];
  // temporal O(1)
  let longitudData = data.length;

  // temporal O(n)
  // espacial O(1)
  for (let i = 0; i < longitudData; i++) {
    // temporal O(1)
    // espacial O(1)
    let payloads = data[i].rocket;
    // temporal O(1)
    // espacial O(n)
    listaDePayloads.push(...payloads.second_stage['payloads']);
  }

  // temporal O(n)
  // espacial O(1)
  for (let i = 0; i < listaDePayloads.length; i++) {
    // temporal O(1)
    // espacial O(1)
    let localPayloadId = listaDePayloads[i].payload_id;
    if (localPayloadId == payloadId) {
      // temporal O(1)
      return true;
    } else {
      // temporal O(1)
      return false;
    }
  }
}

Fredy Daniel Flores Lemus

student•

esta linea de codigo, del algortimo beta, se tomaria como un O(n)?, ya que internamente es un recorrido que se esta haciendo al string.

let payloadIdArray = payloadId.split('');

Marcelo Arias

teacher•

¡Hola Fredy! Sí, en este caso, la función split recorrería (como un for) la longitud de payloadId. Entonces si payloadId fuese "Falcon1", recorrería el string payloadId, 7 veces, y si fuese "Falcon12", recorrería 8 veces, y en "Falcon123", sería 9 veces. El número de instrucciones crece de forma lineal dentro de la función, así que es O(n).

León Sergio Mora Guerrero

student•

No me quedó claro.¿Qué complejidad tiene una transacción con una API?

Marcelo Arias

teacher•

¡Hola León Sergio! En este caso específico consideramos la petición a la API como una sola instrucción, por ello podemos representar await fetch(payloadAPI) como O(1).

León Sergio Mora Guerrero

student•

Muchas gracias por la respuesta!

Juan Camilo Vega

student•

*** SPOILER ALERT: Es un punto del examen ***

Tengo una inquietud con respecto a la evaluación.

En la pregunta:

Determinar el Big-O en espacio de este algoritmo:

function sumatoria(arreglo) { let total = 0; arreglo.forEach(elemento => total += elemento); return total; }

He respondido que el Big-O es O(1), y el sistema me dice que está mal. Si el tamaño del array no cambia y la cantidad de espacio adicional para almacenar la información de la variable 'total' es constante, ¿no se puede afirmar que el Big-O es O(1)? Por descarte, puedo afirmar que la respuesta es O(n), pero realmente no le encuentro sentido. ¿Alguien me puede explicar?

Gracias de antemano a quien se anime a darme una mano con eso!

Juan Pablo Cortés

student•

En este caso por utilizar fetch() la variable respuesta seria O( n ) al analizar la complejidad temporal o sigue siendo O( 1 ). ??

Marcelo Arias

teacher•

¡Hola Juan Pablo!

En este escenario específico consideramos la petición a la API como una sola instrucción en tiempo, por ello podemos representar fetch() como O(1).

No calificaría como O(n) dado que no estamos llamando a la API un número de N veces determinado por el tamaño de la entrada.

Juliana Vega

student•

algoritmoAlfa:

Complejidad Tiempo: O(n*m) Complejidad Espacial: O(n + m) Auxiliar: O(m)

Pienso que el for interno no puede reducirse a constante pues esta iterando sobre payloads, que es creciente. Además, pienso que es un producto con relacion al for externo, puesto que este itera sobre data. Al ser dos datos diferentes me da que es un O(n*m) y no un O(n^2).

Andres Silva Vega

student•

Siendo n el numero de elementos obtenidos de la API, concluyo así:

El algoritmo Alfa tiene una complejidad temporal O(n), pues aunque tiene un for anidado, éste no vuelve a recorrer todos los elementos n. Ese for recorre los elementos de la llave payloads (p) que al menos tiene 1 elemento y máximo 10 por lo que siempre p < n. Como el algoritmo busca el payloadId dentro p, la sumatoria de todos los p son en realidad los n elementos; los for anidados se suman no se multiplican
El algoritmo Beta tiene una complejidad temporal O(m*n) pues recorre todos los elementos n y dentro de este for compara 1 a 1 las letras de payload_id cuya longitud m es != n. Al estar anidados pues m*n.
El algoritmo Delta tiene una complejidad temporal O(2n) pues recorre n almacenando payloads que al menos tienen 1 elemento en una nueva lista p, para luego recorrerla. Simplificando, el tamaño p ≈ n por lo que concluimos que p = n. Al recorrer n y luego p se simplifica en 2n. Espacialmente es O(2n)

franklin yancoba

student•

Para algoritmo alfa = O(n^2)

Para algoritmo beta = O(n^3)

Para algoritmo delta = O(n)

ENRIQUE NIETO MARTINEZ

student•

Alfa

BigO Tiempo -> O(5 + nn) ->O(n^2) BigO Spacio -> O(xx)-> O(x^2) Auxiliar -> O(x^2) - (1+1) -> O(x^2)

async function algoritmoAlfa(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    for (let i = 0; i < data.length; i++) {
        let payloads = data[i].rocket.second_stage['payloads'];
        for (let j = 0; j < payloads.length; j++) {
            if (payloadId == payloads[j].payload_id) {
                return true;
            }
        }
    }
    return false;
}

async function algoritmoBeta(payloadId, payloadAPI) {
    let arreglosCoinciden = (arreglo1, arreglo2) => {
        if (arreglo1.length != arreglo2.length) {
            return false;
        }
        for (let i = 0; i < arreglo1.length; i++) {
            if (arreglo1[i] != arreglo2[i]) {
                return false;
            }
        }
        return true;
    };
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    let payloadIdArray = payloadId.split('');
    for (let i = 0; i < data.length; i++) {
        let payloads = data[i].rocket.second_stage.payloads;
        for (let j = 0; j < payloads.length; j++) {
            if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) {
                return true;
            }
        }
    }
    return false;
}

async function algoritmoDelta(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI);
    let data = await respuesta.json();
    let listaDePayloads = [];
    let longitudData = data.length;

    for (let i = 0; i < longitudData; i++) {
        let payloads = data[i].rocket;
        listaDePayloads.push(...payloads.second_stage['payloads']);
    }

    for (let i = 0; i < listaDePayloads.length; i++) {
        let localPayloadId = listaDePayloads[i].payload_id;
        if (localPayloadId == payloadId) {
            return true;
        } else {
            return false;
        }
    }
}

/**
 * Complejidad Temporal -> O( n^2)
 */


async function algoritmoAlfa(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    for (let i = 0; i < data.length; i++) { //O(n^2)
        let payloads = data[i].rocket.second_stage['payloads']; //O(1)
        for (let j = 0; j < payloads.length; j++) {  //(n)
            if (payloadId == payloads[j].payload_id) { //O(1)
                return true;
            }
        }
    }
    return false;
}

/**
 * Complejidad Temporal -> O( n^2  )
 
 */

async function algoritmoBeta(payloadId, payloadAPI) {
    let arreglosCoinciden = (arreglo1, arreglo2) => { //O(1)
        if (arreglo1.length != arreglo2.length) { //O(1)
            return false;
        }
        for (let i = 0; i < arreglo1.length; i++) { //O(n)
            if (arreglo1[i] != arreglo2[i]) {
                return false;
            }
        }
        return true;
    };
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    let payloadIdArray = payloadId.split(''); //O(1)
    for (let i = 0; i < data.length; i++) { //O(n^2)
        let payloads = data[i].rocket.second_stage.payloads; //O(1)
        for (let j = 0; j < payloads.length; j++) { //(n)
            if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) { //O(1)
                return true;
            }
        }
    }
    return false;
}

/**
 * Complejidad Temporal -> O( n )
 */


async function algoritmoDelta(payloadId, payloadAPI) {
    let respuesta = await fetch(payloadAPI); //O(1)
    let data = await respuesta.json(); //O(1)
    let listaDePayloads = []; //O(1)
    let longitudData = data.length; //O(1)

    for (let i = 0; i < longitudData; i++) { //O(n)
        let payloads = data[i].rocket; //O(1)
        listaDePayloads.push(...payloads.second_stage['payloads']);
    }

    for (let i = 0; i < listaDePayloads.length; i++) { //O(n)
        let localPayloadId = listaDePayloads[i].payload_id; //O(1)
        if (localPayloadId == payloadId) { //O(1)
            return true;
        } else {
            return false;
        }
    }
} 

// .map() recibe a un input ✅
const algoritmoA = (n) => {
  n.map((item) => console.log(item)); // <- Necesitamos analizarlo
};

algoritmoA([1, 2, 3, 4, 5]);

// .map() no recibe al input ❌
const algoritmoB = (n) => {
  ['x', 'y'].map((item) => console.log(item));
};

algoritmoB([1, 2, 3, 4, 5]);

/* 
    Complejidad Temporal -> O( n² ) ya que tiene un ciclo for anidado.
    Complejidad Temporal -> O( n² ) Por la data multinivel que se consigue al procesar la solicitud de la API
    Espacio auxiliar -> O( n² ) El espació auxiliar es este, ya que los valores de entrada son solamente dos pares de String, el procesamiento de esa data está dentro de la función (n² - 2 ) -> (n²)
*/

/**
 * Complejidad temporal => O(n+n + n * (1 + n * (1 + 1)) + 1) = O(2n + n^2) = O(n^2)
 *
 * Complejidad Espacial => O( 1 + 1 + x^2 + x + 1 + x + 1) = O(x^2)
 * Espacio Auxiliar => O(x^2)
 *
 * @param {*} payloadId
 * @param {*} payloadAPI
 * @returns
 */
export default async function algoritmoAlfa(payloadId, payloadAPI) { // Espacial O(1), O(1)
  // temporal O(n) metodo async su tiempo es indeterminado
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI); // entrada de datos?

  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();

  // Temporal O(n)
  // Espacial O(1)
  for (let i = 0; i < data.length; i++) {
    // Temporal O(1)
    // Espacial O(x)
    let payloads = data[i].rocket.second_stage['payloads'];

    // Temporal O(n)
    // Espacial O(1)
    for (let j = 0; j < payloads.length; j++) {
      // Temporal O(1)
      if (payloadId == payloads[j].payload_id) {
        // Temporal O(1)
        return true;
      }
    }
  }
  // Temporal O(1)
  return false;
}

/**
 * Complejidad temporal => O(n^3)
 * Complejidad espacial => O(n^2)
 * Espacio auxiliar => O(n^2)
 * @param {*} payloadId 
 * @param {*} payloadAPI 
 * @returns 
 */
export default async function algoritmoBeta(payloadId, payloadAPI) { // Espacial O(1), O(1)

  // Temporal O(1)
  // Espacial O(1)
  let arreglosCoinciden = (arreglo1, arreglo2) => {
    // Temporal O(1)
    if (arreglo1.length != arreglo2.length) {
      // Temporal O(1)
      return false;
    }
    // Temporal O(n)
    // Espacial O(1)
    for (let i = 0; i < arreglo1.length; i++) {
      // Temporal O(1)
      if (arreglo1[i] != arreglo2[i]) {
        // Temporal O(1)
        return false;
      }
    }
    // Temporal O(1)
    return true;
  };

  // Temporal O(n)
  // Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI);// entrada de datos?

  // Temporal O(n)
  // Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();

  // Temporal O(1)
  // Espacial O(1)
  let payloadIdArray = payloadId.split('');

  // Temporal O(n)
  // Espacial O(1)
  for (let i = 0; i < data.length; i++) {
    // Espacial O(1)
    let payloads = data[i].rocket.second_stage.payloads;
    // Temporal O(n)
    // Espacial O(1)
    for (let j = 0; j < payloads.length; j++) {
      // Temporal O(n) el metodo arreglosCoinciden es temporal O(n)
      if (arreglosCoinciden(payloadIdArray, payloads[j].payload_id.split(''))) {
        // Temporal O(1)
        return true;
      }
    }
  }
  // Temporal O(1)
  return false;
}

/**
 * Complejidad temporal => O(n + n + n + n) = O(n)
 * Complejidad Espacial => O(x^2)
 * Espacio auxiliar => O(x^2)
 * @param {*} payloadId 
 * @param {*} payloadAPI 
 * @returns 
 */
export default async function algoritmoDelta(payloadId, payloadAPI) { // Espacial O(1), O(1)

  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let respuesta = await fetch(payloadAPI); // entrada de datos?
  // temporal O(n)
  // Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetos
  let data = await respuesta.json();
  // temporal O(1)
  // espacial O(1)
  let listaDePayloads = [];
  // temporal O(1)
  let longitudData = data.length;

  // temporal O(n)
  // espacial O(1)
  for (let i = 0; i < longitudData; i++) {
    // temporal O(1)
    // espacial O(1)
    let payloads = data[i].rocket;
    // temporal O(1)
    // espacial O(n)
    listaDePayloads.push(...payloads.second_stage['payloads']);
  }

  // temporal O(n)
  // espacial O(1)
  for (let i = 0; i < listaDePayloads.length; i++) {
    // temporal O(1)
    // espacial O(1)
    let localPayloadId = listaDePayloads[i].payload_id;
    if (localPayloadId == payloadId) {
      // temporal O(1)
      return true;
    } else {
      // temporal O(1)
      return false;
    }
  }
}

Complejidad de algoritmos en búsqueda de payloads de SpaceX

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

Complejidad espacial

Análisis de Complejidad de Algoritmos: Tiempos y Eficiencia

Complejidad temporal en práctica

Complejidad espacial en práctica

El estado de la complejidad

Análisis asintótico

Introducción a análisis asintótico

Notación Big-O

Cálculo de la notación Big-O

Evaluación de complejidad temporal con Big-O

Evaluación de complejidad espacial con Big-O Avanzado

Recomendaciones

Recomendaciones para la evaluación de algoritmos

Repaso de Complejidad Algorítmica y Notación Big-O

Cierre del curso

Bonus

Complejidad de algoritmos en búsqueda de payloads de SpaceX