Ahora que tenemos una comprensión básica de la notación Big-O gracias al post anterior (te invito a que lo revises), podemos comenzar a buscar cálculos algo más costosos para ir entendiendo como se evaluan los algoritmos a grandes rasgos.

¡Imagina que estás organizando una gran fiesta y tienes una lista de invitados! Cada invitado tiene una edad determinada y quieres ordenar la lista de invitados por edad, de menor a mayor. Podrías optar por la estrategia de fuerza bruta, que consiste en comparar la edad de cada invitado con la de todos los demás, uno por uno.

Este método en programación se conoce como “Bubble Sort” o “Ordenamiento de Burbuja” 📋, y es famoso por ser bastante lento… bueno si espantosamente lento en rendimiento claro está. Veamos su implementación:

1. function bubbleSort(peopleInvited) {
2.  for (var i = 0; i < peopleInvited.length; i++) {
3.    // Notice that j < (length - i)
4.    for (var j = 0; j < peopleInvited.length - i - 1; j++) {
5.      // Compare the adjacent positions
6.      if (peopleInvited[j] > peopleInvited[j + 1]) {
7.        // Swap the numbers
8.        var tmp = peopleInvited[j];
9.        peopleInvited[j] = peopleInvited[j + 1];
10.       peopleInvited[j + 1] = tmp;
11.     }
12.    }
13.  }
14.
15.  return peopleInvited;
16. }

En el ejemplo de código del post anterior vimos la implementación del método find(array, value) donde teníamos un bucle for, por lo que nuestra notación Big-O era bastante sencilla, pero en este ejemplo tenemos dos bucles for y están anidados uno dentro del otro.

❓ ¿Qué significa esto para nuestro rendimiento?

🎥 Vamos a desglosarlo un poco:

• Línea 2: Esto es como contar a todos los invitados de la fiesta, que llamaremos n (cantidad de invitados). Esto sería O(n).
• Línea 4: Aquí estamos contando de nuevo, pero esta vez nos saltamos al último invitado que ya hemos comparado anteriormente. Esto sería O(n-1).
• Líneas 6, 8, 9, 10 y 15: Podríamos pensar que esto se ejecuta para cada elemento de la lista de invitados (que en el peor de los casos es así), pero en realidad evaluamos el tiempo de ejecución de forma aislada, es decir, de forma aislada esta sentencia if se ejecuta una vez. Esto se llama como hemos visto tiempo constante y lo escribimos como O(1). A medida que aumenta el tamaño de los datos (n), no cambia la cantidad de veces que se ejecuta este fragmento de código.

😕 Se que esta última parte pueda causar algún tipo de confusión al decir ejecutarse de forma aíslada, hacemos una breve explicación previo a continuar para ir entendiendo como funciona todas estas conclusiones que vamos descubriendo:

Lo que el texto intenta decir es que en un análisis aislado, la sentencia if y las líneas de código dentro del bloque if (líneas 8, 9 y 10) tienen un tiempo de ejecución constante, es decir, O(1). Esto significa que el número de operaciones que estas líneas de código realizan no depende del tamaño de la entrada (en este caso, la longitud de peopleInvited).

Sin embargo, es importante destacar que esto no significa que la sentencia if y el bloque de código dentro de ella se ejecuten solo una vez durante todo el algoritmo. De hecho, se ejecutan muchas veces, dependiendo de cómo estén organizados los elementos en el array peopleInvited.

✍️ Para ser más específico:

• El bucle interno en la línea 4 se ejecuta n-1 veces en la primera iteración, luego n-2 veces, luego n-3 veces, y así sucesivamente.
• La sentencia if en la línea 6 se evalúa en cada iteración del bucle interno. Es decir, se evalúa (n-1) + (n-2) + (n-3) + ... + 1 veces en total, que es igual a n(n-1)/2 veces.
• Las líneas 8, 9, y 10 (que realizan el intercambio de elementos) solo se ejecutan cuando la condición en la línea 6 es verdadera, lo cual puede variar.

🎯 Cuando se habla de la notación Big-O, estamos interesados en cómo crece el tiempo de ejecución a medida que el tamaño de la entrada aumenta.

Ahora, la parte divertida es juntarlo todo. Pero antes de hacerlo, necesitamos recordar una regla crucial de la notación Big-O:

• 💡 Simplificar, simplificar y simplificar. Nos importa la tendencia general a largo plazo, no los detalles minuciosos del algoritmo.

🤝 Así que, a la hora de simplificar, seguimos estas reglas :

1. O(5) sigue siendo un tiempo constante y se escribirá como O(1).
2. O(2n) sigue siendo un tiempo lineal y se escribirá como O(n).
3. O(n - 3) => O(n)
4. O(n^3 + n^2) => O(n^3)
5. O(150x + 650y) => O(x + y) “x” e “y” son valores diferentes, por lo que no puedo tirarlos, ni combinarlos.

Entonces, de vuelta a nuestra fiesta. La línea 4 de O(n-1) se simplifica a O(n) porque estamos desechando el término menos significativo. Las líneas 6, 8, 9, 10 y 15 son términos de tiempo constante O(1), y todos son menos significativos, por lo que también podemos descartarlos. Nos quedamos con la O(n) del bucle exterior y la O(n) del bucle interior.

Ahora bien, ¿qué hacemos con estos dos valores de n? ¿Los sumamos o los multiplicamos? Bueno, eso depende de si los bucles están “anidados” o son “adyacentes”.

• Si están anidados, como en nuestro algoritmo de ordenamiento, los multiplicamos.
• Si son adyacentes, los sumaríamos.

Por lo tanto, siguiendo todas estas reglas, la complejidad del algoritmo para acomodar los invitados por edad, es decir, nuestro algoritmo de Bubble Sort o fuerza bruta, es O(n*n), que también podemos escribirlo como O(n^2).

🧠 Esto significa que si tuvieras 100 invitados en tu fiesta, terminarías haciendo alrededor de 10,000 comparaciones en el peor de los casos (100 invitados * 100 comparaciones por invitado = 10,000 comparaciones). Y si tuvieras 1,000 invitados, ¡terminarías haciendo alrededor de 1,000,000 de comparaciones! Como puedes ver, el rendimiento de Bubble Sort se deteriora muy rápidamente a medida que el número de invitados aumenta.

🗞️ Además te dejo un ejemplo del algoritmo para que puedas visualizarlo mejor a su funcionamiento:

• En cada “paso” del algoritmo, se comparan los años de dos invitados consecutivos. Si el primer invitado es mayor que el segundo, intercambias sus posiciones en la lista. De esta manera, el invitado de mayor edad “burbujea” hacia el final de la lista a medida que se ejecuta cada paso. Este proceso se repite desde el inicio de la lista hasta que no se necesiten más intercambios, lo que indica que la lista está completamente ordenada​.

Aquí está el proceso paso a paso con la lista de edades de los 5 invitados que usaremos de ejemplos con sus edades [(35, 22, 45, 30, 26)]:

1️⃣ Primer Paso

(35, 22, 45, 30, 26) → (22, 35, 45, 30, 26) // Se intercambian 35 y 22 porque 35 > 22

(22, 35, 45, 30, 26) → (22, 35, 45, 30, 26) // No se intercambian 35 y 45 porque 35 < 45

(22, 35, 45, 30, 26) → (22, 35, 30, 45, 26) // Se intercambian 45 y 30 porque 45 > 30

(22, 35, 30, 45, 26) → (22, 35, 30, 26, 45) // Se intercambian 45 y 26 porque 45 > 26

2️⃣ Segundo Paso

(22, 35, 30, 26, 45) → (22, 35, 30, 26, 45) // No se intercambian 22 y 35 porque 22 < 35

(22, 35, 30, 26, 45) → (22, 30, 35, 26, 45) // Se intercambian 35 y 30 porque 35 > 30

(22, 30, 35, 26, 45) → (22, 30, 26, 35, 45) // Se intercambian 35 y 26 porque 35 > 26

(22, 30, 26, 35, 45) → (22, 30, 26, 35, 45) // No se intercambian 35 y 45 porque 35 < 45

3️⃣ Tercer Paso

(22, 30, 26, 35, 45) → (22, 30, 26, 35, 45) // No se intercambian 22 y 30 porque 22 < 30

(22, 30, 26, 35, 45) → (22, 26, 30, 35, 45) // Se intercambian 30 y 26 porque 30 > 26

(22, 26, 30, 35, 45)

Es por esto que, aunque Bubble Sort es un algoritmo fácil de entender e implementar, rara vez se usa en la práctica para listas grandes. Existen otros algoritmos de ordenamiento más eficientes, como Quicksort, Mergesort y Heapsort, que tienen una mejor complejidad de tiempo en el peor de los casos.

¡Y ahí lo tienes! Ahora puedes lucirte en la próxima fiesta de programadores hablando de la notación Big-O y su aplicación en el Bubble Sort. Y si alguien te pregunta cómo lo aprendiste, puedes decirles que fue en una Fiesta con invitados 🥳.

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

Espero verte pronto en la próxima edición donde veremos los diferentes tipos de complejidades de tiempo más a detalle. 👋