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:
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:
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:
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?
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!
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].
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
Jaaayz
Michael_19
