La complejidad algorítmica parte de la idea de comprender cómo se mide y analiza la eficiencia de los algoritmos. Puede que esto parezca algo que no es una tarea fácil, pero una vez te lo expliquemos, seguro vas a entenderlo mejor. Veamos de qué se trata y cómo hacer análisis de complejidad algorítmica.

¿Qué encontrarás en este post?

¿Qué es la complejidad algorítmica?

La complejidad algorítmica es una medida de la eficiencia de un algoritmo, en términos de tiempo y espacio. En otras palabras, evalúa cuánto tiempo tarda un algoritmo en ejecutarse y cuánta memoria requiere, en función del tamaño de la entrada. Este análisis nos permite comparar diferentes algoritmos y elegir el más adecuado para una tarea específica.

Existen dos tipos principales de complejidad:

Complejidad temporal: Mide el tiempo que tarda un algoritmo en ejecutarse.
Complejidad espacial: Mide la cantidad de memoria que un algoritmo necesita para ejecutarse.

La notación O grande: el lenguaje de la complejidad algorítmica

La notación O grande, también llamada Big O, es la forma más común de expresar la complejidad algorítmica. Esta notación nos dice cómo crece el tiempo de ejecución o el uso de memoria de un algoritmo a medida que aumenta el tamaño de la entrada. Algunos de los órdenes de complejidad más comunes son:

O(1): Complejidad constante. El tiempo de ejecución no cambia, sin importar el tamaño de la entrada.
O(log n): Complejidad logarítmica. El tiempo de ejecución crece lentamente a medida que aumenta el tamaño de la entrada.
O(n): Complejidad lineal. El tiempo de ejecución crece de manera proporcional al tamaño de la entrada.
O(n log n): Complejidad casi lineal. Es un poco más lento que O(n), pero mucho más eficiente que O(n^2).
O(n^2): Complejidad cuadrática. El tiempo de ejecución crece de manera exponencial a medida que aumenta el tamaño de la entrada.

Ejemplos de análisis de complejidad algorítmica

Para entender mejor cómo funciona el análisis de complejidad algorítmica, veamos algunos ejemplos de aplicación:

Búsqueda lineal (O(n)): En una búsqueda lineal el algoritmo revisa cada elemento de una lista hasta encontrar el que está buscando. Si la lista tiene n elementos, en el peor de los casos, el algoritmo tendrá que revisar todos los elementos, lo que da una complejidad de O(n).

function buscarElemento(arr, objetivo) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === objetivo) {
      return i;
    }
  }
  return -1; // No encontrado
}

Este código implementa un algoritmo de búsqueda lineal para encontrar un elemento en un array. La búsqueda lineal recorre cada elemento del array uno por uno, desde el primer elemento hasta el último, comparando cada elemento con el objetivo de búsqueda. Si encuentra el objetivo, devuelve la posición (índice) de ese elemento en el array. Si no lo encuentra después de revisar todos los elementos, devuelve -1, lo que indica que el objetivo no está en el array.

Búsqueda binaria (O(log n)): La búsqueda binaria es mucho más eficiente, pero solo funciona en listas ordenadas. En lugar de revisar cada elemento, el algoritmo divide la lista en dos partes, comparando el elemento medio con el objetivo. Si el objetivo es menor, descarta la mitad superior; si es mayor, descarta la mitad inferior. Este proceso se repite hasta encontrar el objetivo o hasta que no queden más elementos por revisar.

function busquedaBinaria(arr, objetivo) {
  let inicio = 0;
  let fin = arr.length - 1;

  while (inicio <= fin) {
    const medio = Math.floor((inicio + fin) / 2);

    if (arr[medio] === objetivo) {
      return medio;
    } else if (arr[medio] < objetivo) {
      inicio = medio + 1;
    } else {
      fin = medio - 1;
    }
  }

  return -1; // No encontrado
}

Este código implementa un algoritmo de búsqueda binaria, que es una técnica eficiente para encontrar un elemento en un array ordenado. En lugar de revisar cada elemento uno por uno, como en la búsqueda lineal, la búsqueda binaria divide repetidamente el array en mitades para reducir el área de búsqueda. Esto le permite encontrar el elemento en un tiempo logarítmico, lo que es mucho más rápido para grandes conjuntos de datos.

En este caso, la complejidad algorítmica es O(log n) porque cada vez que el algoritmo realiza una comparación, reduce el tamaño del problema a la mitad.

En KeepCoding, te enseñamos a dominar estas y otras técnicas para que puedas enfrentarte a cualquier desafío en el mundo de la programación. Si quieres llevar tus habilidades al siguiente nivel, nuestros bootcamps son la puerta de entrada a una carrera exitosa , donde te esperan altos salarios y estabilidad laboral. Únete al bootcamp en big data y data science ahora mismo. ¡No pierdas la oportunidad de transformar tu vida!

¿Qué es la complejidad algorítmica?: aprende a hacer análisis