Herramientas de usuario
algoritmos-oia:estructuras:union-find
Diferencias
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 | ||
|
algoritmos-oia:estructuras:union-find [2017/12/31 21:23] sebach [Optimizaciones] |
algoritmos-oia:estructuras:union-find [2017/12/31 21:24] (actual) 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)$. | + | 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 casi $O(m)$. |
| ==== Código ==== | ==== Código ==== | ||
algoritmos-oia/estructuras/union-find.1514755431.txt.gz · Última modificación: 2017/12/31 21:23 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
