Complejidad de algoritmos en búsqueda de payloads de SpaceX

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