Tu código funciona, ¿pero es eficiente?

Hablemos un poco de Big O Notation y los loops.

hace 3 meses   •   4 min de lectura

Por Andrés Tuñón

Hace unos días me enfrente a un caso en el que debía recorrer un árbol con múltiples hijos, múltiples padres y cada nodo podía repetirse múltiples veces.

Evitaba de todas las formas posibles tener que recorrer el árbol a través de sus hijos, pero llegó el momento en que debía recrear la información desde un JSON del API.

El primer algoritmo resultante fue 3 ciclos anidados y funcionaba; pero obviamente no era eficiente, es un O(n^3). Le agregué mecanismos para reducir la cantidad de elementos que debe buscar en sus arreglos (memoization), pero me quedé con la duda: ¿Realmente es eficiente? Les muestro una función similar a la mía a continuación:

Código
Código

A partir de esto me pareció interesante volver a ver un conjunto de videos que resume muy bien los conceptos de Big O Notation, aquí un resumen (si deseas ver el video, ve directo a las referencias ¡es buenísimo!)

Big O Notation ayuda a calcular la complejidad de un algoritmo y a partir de ese resultado puedes encontrar una "mejor" (en tiempo y espacio) implementación.

Lo que te importa es el peor de los casos, por esto tiendes a simplificar la función resultante.

Para ir calculando debes ir contando las operaciones, por ejemplo para un for-loop:

un simple for-loop
un simple for-loop

Tienes 1 operación dentro que se ejecuta N veces, por lo tanto seria O(1N) que simplificándolo se vuelve O(N).

En el caso hipotético que la N fuera 5 siempre, se reduce muchísimo la complejidad; ya que siempre se ejecutará 5 veces sin importar N.

Ahora si ejecutas 2 for-loops uno seguido del otro:

2 for-loops en serie
2 for-loops en serie

Siguiendo el patrón sería la ejecución de 2 loops iguales; es decir, se suman y  sería O(2N), que simplificándolo es O(N).

Ahora ¿qué pasa si los anidas?

2 for-loops anidados
2 for-loops anidados

Deberían multiplicarse, ya que es N veces M veces y eso resulta en O(N*M). Por supuesto que si N y M fueran iguales sería O(N^2).

Conclusión

Si le damos un vistazo al código otra vez, puedes notar que recorro todos los nodos 1 sola vez, luego dentro recorro otra colección de padres para 'linkear'.

Si no me equivoco, esto seria algo como O(nodes * parents * savedParents). ¡No está mal!

Código
Código

Pero luego me doy cuenta que el spread operator tiene una complejidad de O(N) y las funciones recursivas dependen del árbol de llamadas (en este caso O(children^children) creo; ya que la recursión puede crecer exponencialmente dependiendo la cantidad de hijos que tenga el siguiente hijo).

Me voy a mojar y diré que en total seria algo como O[(nodes * parents * savedParents + spreads)*children^children].

Js Developer
Js Developer

Aquí ya simplemente te doy la excusa de que es Functional Programming, como buen Javascript Developer.

Lo importante es que se debe evitar los loops anidados y si los vas a usar, con mucho cuidado.

Referencias

Video de donde extraje la gran parte de información
No podia faltar
No podia faltar
What’s the time complexity of JavaScript spread syntax in arrays?
I was wondering what is the time complexity of using spread with an array in JavaScript. Is it linear O(n) or constant O(1)?Example of syntax below:let lar = Math.max(...nums)
Spread Operator
Determining complexity for recursive functions (Big O notation)
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these
Caso de Funciones Recursivas
Advent of Code - Día 6
Mi solución para el día 6.
Primera vez que estuve obligado a preocuparme por este tema y un ejemplo con números

Corre la voz

Sigue leyendo