Diseñar y construir algoritmos es una parte integral del desarrollo de software. Aunque el objetivo principal de cada algoritmo es resolver un problema particular, es esencial considerar cómo un algoritmo realiza su trabajo y cuántos recursos necesita para hacerlo, ya que en definitiva esto en algún momento se transformará en costos para nuestro cliente. Estos recursos incluyen tanto el tiempo de cálculo, que se refiere a cuánto tiempo se necesita para ejecutar un algoritmo, como el espacio de memoria, que se refiere a cuánto almacenamiento requiere el algoritmo. Esta necesidad de analizar la eficiencia de los algoritmos da lugar al estudio de la complejidad algorítmica.

La complejidad algorítmica es una métrica que nos permite cuantificar de manera precisa el rendimiento de un algoritmo en función del tamaño de su entrada. Esto es crucial para comprender y predecir cómo se comportará nuestro algoritmo con diferentes volúmenes de datos. Por ejemplo, un algoritmo que funcione bien con pequeñas cantidades de datos puede ser ineficiente cuando se le da un conjunto de datos mucho más grande, y a veces no es que necesite ser del orden de millones para que ya no sea tan performante como esperamos.

Además, la comprensión de la complejidad algorítmica es de vital importancia durante el proceso de entrevistas técnicas. Los entrevistadores suelen preguntar acerca de la complejidad de los algoritmos para evaluar la habilidad del candidato para escribir código eficiente y para valorar su capacidad de tomar decisiones informadas sobre los trade-offs entre tiempo y espacio.

En este artículo, examinaremos más de cerca la notación Big-O, que se utiliza para describir la complejidad algorítmica, y también veremos las notaciones Big-Theta y Big-Omega. Espero que este post te ayude a mejorar tu comprensión de estos conceptos fundamentales en ciencias de la computación. ¡Vamos a ello!

⏳ Complejidad Algorítmica ¿Qué es?

Cada algoritmo o conjunto de instrucciones requiere un tiempo y espacio para ejecutarse, de manera que, cuando diseñamos algoritmos para solucionar nuestros problemas, es importante considerar su complejidad temporal y espacial.

Por lo general, solo escuchamos hablar de la notación Big-O cuando hablamos de la complejidad y el rendimiento algorítmico, ¡Y… si, hay una razón para esto! Pero también es importante comprender que existen Big-θ (Big-Theta) y Big-Ω (Big-Omega).

La notación Big-O describe el rendimiento o complejidad más lenta de un algoritmo. Nos dice cuánto tiempo o espacio puede llegar a necesitar un algoritmo en el peor de los casos.

Por otro lado, Big-Ω (Big-Omega) se utiliza para describir la complejidad espacial y temporal en el mejor de los casos de un algoritmo. Este límite inferior asintótico se refiere al tiempo o espacio mínimo que requiere un algoritmo. En cuanto a Big-θ (Big-Theta), describe la complejidad espacial y temporal promedio de un algoritmo, lo que significa cuánto tiempo o espacio requiere un algoritmo en promedio para ejecutarse.

Entonces a medida que aumenta el tamaño de nuestros datos ¿Cómo afecta al rendimiento del algoritmo o a los requisitos de espacio del mismo?

Vamos a ilustrar esto con un ejemplo sencillo.

const find = (array, value) => {
  for (const element of array) {
    if (element === value) {
      return true;
    }
  }
  
  return false;
}

En esta función buscamos un valor específico. El primer argumento es una colección de valores para buscar y el segundo argumento es el valor que estamos buscando.

Estamos usando un ciclo for para iterar a través de cada valor en la colección y verificar si es igual al valor objetivo. Si el valor está en la matriz, devuelve true; de lo contrario, devuelve false como mostramos en los siguientes fragmentos de código.

const array = [1, 2, 3, 4, 5];
const value = 3;

const result = find(array, value);

console.log(result); // esto imprimirá "true" en la consola

const array = [1, 2, 3];
const value = 4;

const result = find(array, value);

console.log(result); // esto imprimirá "false" en la consola

⌚ ¿Cuánto tiempo tardará en ejecutarse este algoritmo? Bueno debemos pensar, ¿cuál es nuestro peor escenario?

Big-O 1️⃣

En el peor de los casos (Big-O), el valor que estamos buscando no se encuentra en la matriz, y debemos recorrer todos los elementos de la matriz. Esto nos lleva a una complejidad temporal de O(n). A medida que aumenta la longitud de la matriz, el tiempo necesario para ejecutar este algoritmo aumenta de manera proporcional.

Si tenemos una matriz con 10 elementos, la cantidad máxima de veces que iteraremos a través de nuestra matriz buscando este elemento es justamente 10. Del mismo modo, si tenemos una matriz con 100 elementos, la cantidad máxima de veces que iteraremos a través de nuestra matriz en busca de este elemento es 100.

Este tipo de algoritmo se conoce como algoritmo de tiempo lineal y se representa como O(n) donde el rendimiento del algoritmo empeora proporcionalmente al tamaño de la entrada, o dicho de otra manera el tiempo de ejecución del algoritmo aumenta proporcionalmente al tamaño de la entrada.

Big-Ω 2️⃣

En el mejor de los casos (Big-Ω), el valor que buscamos se encuentra en el primer elemento de la matriz. Esto nos daría una complejidad temporal de O(1).

Big-θ 3️⃣

Para el caso promedio (Big-θ), suponemos que debemos buscar en la mitad de la matriz antes de encontrar nuestro valor. Esto nos daría una complejidad temporal de O(n/2), pero en la notación Big-O, las constantes se ignoran, por lo que también sería O(n).

Aunque es más común hablar sobre Big-O en la industria y en las entrevistas técnicas, entender Big-Ω y Big-θ te permitirá tener una imagen más completa de cómo se desempeñan los algoritmos en diferentes situaciones.

No debería necesitar conocer Big-θ y Big-Ω para una entrevista técnica, pero es bueno estar familiarizado con ellos.

En futuros posts, exploraremos en detalle ejemplos más complicados y cómo identificar la complejidad algorítmica. ¡Espero que te unas a la serie!

También podes buscar la versión en inglés dentro del Blog Rooftop

¡Hasta la próxima! 👋