Determinando la complejidad un algoritmo avanzado

18/18

Lectura

Determinando la complejidad de un algoritmo más avanzado

cover

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

Aportes 6

Preguntas 3

Ordenar por:

Los aportes, preguntas y respuestas son vitales para aprender en comunidad. Regístrate o inicia sesión para participar.

💚 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!

  1. El Algoritmo Alfa tiene una complejidad temporal simplificada de O(n^2) porque tiene un ciclo for dentro de otro for.
  2. El Algoritmo Beta tiene una complejidad temporal de O (n^3)
  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 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²)
*/

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.

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;
    }
  }
}

Alfa

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