💭 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:
asyncfunctionalgoritmoAlfa(payloadId, payloadAPI){let respuesta =awaitfetch(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){returntrue;}}}returnfalse;}
Algoritmo Beta
asyncfunctionalgoritmoBeta(payloadId, payloadAPI){letarreglosCoinciden=(arreglo1, arreglo2)=>{if(arreglo1.length!= arreglo2.length){returnfalse;}for(let i =0; i < arreglo1.length; i++){if(arreglo1[i]!= arreglo2[i]){returnfalse;}}returntrue;};let respuesta =awaitfetch(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(''))){returntrue;}}}returnfalse;}
Algoritmo Delta
asyncfunctionalgoritmoDelta(payloadId, payloadAPI){let respuesta =awaitfetch(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){returntrue;}else{returnfalse;}}}
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.
Complejidad de algoritmos en búsqueda de payloads de SpaceX
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)
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!
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
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²)
*/
¡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).
¡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).
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!
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í:
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)
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 ✅constalgoritmoA=(n)=>{ n.map((item)=>console.log(item));// <- Necesitamos analizarlo};algoritmoA([1,2,3,4,5]);// .map() no recibe al input ❌constalgoritmoB=(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))).
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 */exportdefaultasyncfunctionalgoritmoAlfa(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 objetoslet respuesta =awaitfetch(payloadAPI);// entrada de datos?// temporal O(n)// Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetoslet 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)returntrue;}}}// Temporal O(1)returnfalse;}/**
* Complejidad temporal => O(n^3)
* Complejidad espacial => O(n^2)
* Espacio auxiliar => O(n^2)
* @param{*}payloadId * @param{*}payloadAPI * @returns */exportdefaultasyncfunctionalgoritmoBeta(payloadId, payloadAPI){// Espacial O(1), O(1)// Temporal O(1)// Espacial O(1)letarreglosCoinciden=(arreglo1, arreglo2)=>{// Temporal O(1)if(arreglo1.length!= arreglo2.length){// Temporal O(1)returnfalse;}// 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)returnfalse;}}// Temporal O(1)returntrue;};// Temporal O(n)// Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetoslet respuesta =awaitfetch(payloadAPI);// entrada de datos?// Temporal O(n)// Espacial O(n^2) son matrices el nivel de complejidad del arreglo de objetoslet 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)returntrue;}}}// Temporal O(1)returnfalse;}/**
* Complejidad temporal => O(n + n + n + n) = O(n)
* Complejidad Espacial => O(x^2)
* Espacio auxiliar => O(x^2)
* @param{*}payloadId * @param{*}payloadAPI * @returns */exportdefaultasyncfunctionalgoritmoDelta(payloadId, payloadAPI){// Espacial O(1), O(1)// temporal O(n)// Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetoslet respuesta =awaitfetch(payloadAPI);// entrada de datos?// temporal O(n)// Espacial O(x^2) son matrices el nivel de complejidad del arreglo de objetoslet 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)returntrue;}else{// temporal O(1)returnfalse;}}}
