Complejidad de algoritmos en búsqueda de payloads de SpaceX
Contenido del curso
Complejidad algorítmica
Análisis asintótico
Recomendaciones
Bonus
Complejidad de algoritmos en búsqueda de payloads de SpaceX
Contenido del curso
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.
Marcelo Arias
Profesor
Carlos Delgado
Estudiante
Angel Solis
Estudiante
Leonardo Buezo
Estudiante
Lautaro Els
Estudiante
Christian Boffill
EstudianteMarcelo Arias
Profesor
Daniel Omar Hernández Muñoz
Estudiante
Marco Antonio Miranda Sandoval
Estudiante
Diego Reyes Cabrera
Estudiante
Anfernee Valera
Estudiante
Luis Rogelio Reyes Hernandez
Estudiante
Fredy Daniel Flores Lemus
EstudianteMarcelo Arias
Profesor
León Sergio Mora Guerrero
EstudianteMarcelo Arias
ProfesorLeón Sergio Mora Guerrero
Estudiante
Juan Camilo Vega
Estudiante
Juan Pablo Cortés
EstudianteMarcelo Arias
Profesor
Juliana Vega
Estudiante
Andres Silva Vega
Estudiante
franklin yancoba
Estudiante
ENRIQUE NIETO MARTINEZ
Estudiante💚 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!
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
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!
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; } } }
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
¡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:
O(n)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))).
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.
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
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.
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²) */
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; } } }
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('');
¡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).
No me quedó claro.¿Qué complejidad tiene una transacción con una API?
¡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).
Muchas gracias por la respuesta!
*** 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!
En este caso por utilizar fetch() la variable respuesta seria O( n ) al analizar la complejidad temporal o sigue siendo O( 1 ). ??
¡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.
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).
Siendo n el numero de elementos obtenidos de la API, concluyo así:
Para algoritmo alfa = O(n^2)
Para algoritmo beta = O(n^3)
Para algoritmo delta = O(n)
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)