Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa Última revisión Ambos lados, revisión siguiente | ||
algoritmos-oia:estructuras:union-find [2017/12/31 21:22] sebach [Código] |
algoritmos-oia:estructuras:union-find [2017/12/31 21:24] sebach [Optimizaciones] |
||
---|---|---|---|
Línea 27: | Línea 27: | ||
**Una optimización más**: Podemos pensar que cada conjunto es un árbol! El representante será la raíz, saber la raíz de un árbol (o sea el representante de un conjunto) es ir yendo a los padres de cada elemento, y agregar el conjunto de representante $rx$ al de representante $ry$, es decirle a $rx$ que su padre es $ry$, que sería como colgar el árbol de $rx$ de la raíz $ry$. Si colgamos el árbol de menor tamaño al de mayor, como antes con las listas, haremos menos operaciones. Y si además de esto, al buscar el padre de un elemento recursivamente, lo actualizamos cuando encontremos la raíz, las alturas de los árboles se achican muchísimo, y al calcular el representante de un elemento dos veces por ejemplo, en la primera lo encontramos, se lo asignamos como padre, y luego al buscar el representante es subir una sola vez. | **Una optimización más**: Podemos pensar que cada conjunto es un árbol! El representante será la raíz, saber la raíz de un árbol (o sea el representante de un conjunto) es ir yendo a los padres de cada elemento, y agregar el conjunto de representante $rx$ al de representante $ry$, es decirle a $rx$ que su padre es $ry$, que sería como colgar el árbol de $rx$ de la raíz $ry$. Si colgamos el árbol de menor tamaño al de mayor, como antes con las listas, haremos menos operaciones. Y si además de esto, al buscar el padre de un elemento recursivamente, lo actualizamos cuando encontremos la raíz, las alturas de los árboles se achican muchísimo, y al calcular el representante de un elemento dos veces por ejemplo, en la primera lo encontramos, se lo asignamos como padre, y luego al buscar el representante es subir una sola vez. | ||
+ | La **complejidad** es un poco más baja que $O(m*log(m))$, podría decirse que es **lineal**: para $O(m)$ operaciones el tiempo que lleva procesarlas es $O(m)$. | ||
==== Código ==== | ==== Código ==== |