Solución de tiempo amortizado $O(\log^* n)$

Cuando se realiza una operación $Find(v)$, se visitan todos los ancestros de $v$ hasta llegar a la raíz $x$: $v = v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{r-2} \rightarrow v_{r-1} \rightarrow v_r = x$. Para agilizar las futuras operaciones de $Find$, no nos cuesta nada colgar a todos los nodos del camino, $v_1, \ldots, v_{r-2}$, directamente de $v_r = x$ (por ejemplo, puede hacerse a la vuelta de la recursión). Así, las futuras operaciones $Find(v_i)$ tomarán tiempo $O(1)$. Asimismo, se agilizarán los $Find(u)$ sobre otros descendientes $u$ de algún $v_i$.

--> imagen

¿Qué impacto tiene esta mejora sobre los tiempos de $Find$? En el peor caso, ninguno, pues si bien una aplicación de $Find$ mejora el tiempo de las siguientes operaciones $Find$, el primer $Find$ puede costar $O(\log n)$ (por ejemplo, si hacemos $n-1$ $Union$ y luego el primer $Find$). Necesitamos entonces realizar un análisis amortizado.

Considere una secuencia $S$ de operaciones $Union$ y $Find$, y llamemos $S'$ a la secuencia $S$ sin las operaciones $Find$. Definiremos el rango de un nodo $v$, $r(v)$, como la altura del subárbol luego de realizar las operaciones de $S'$ (o bien, de aplicar $S$ pero sin la mejora que acabamos de describir para $Find$). Hablaremos del rango de los nodos mientras analizamos la secuencia verdadera $S$, pero debe recordar que $r(v)$ es fijo e independiente del punto de $S$ que estemos considerando.

Una propiedad importante es que, como vimos en la subsección anterior, un nodo de rango $r$ tiene al menos $2^r$ nodos en su subárbol (el que resulta de aplicar $S'$). Como, en estos árboles, dos nodos $u$ y $v$ de rango $r$ no pueden descender uno del otro (pues entonces uno sería más alto que el otro), sus subárboles deben ser disjuntos. Por lo tanto, no puede haber más de $\frac{n}{2^r}$ nodos de rango $r$.

Otra propiedad importante es que, si en algún momento de $S$, $u$ desciende de $v$, entonces $r(u) < r(v)$. Esto ocurre porque sólo la operación $Union$ crea nuevas descendencias (al colgar $x$ de $y$, todo descendiente de $x$ pasa a ser también descendiente de $y$), mientras que sólo la operación $Find$ destruye descendencias (al colgar todos los $v_i$ directamente de $x$, los descendientes de $v_i$ dejan de ser descendientes de $v_{i+1},\ldots,v_{r-1}$). Por lo tanto, en $S'$, donde se han eliminado los $Find$, $u$ también se hará descendiente de $v$ y se mantendrá así hasta el final. Como $u$ desciende de $v$ al final de $S'$, debe ser $r(u) < r(v)$.

Para nuestro análisis, definiremos la función $F(i)$ como $F(0)=1$ y $F(i) = 2^{F(i-1)}$. Esta función crece muy rápidamente:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline i & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline F(i) & 1 & 2 & 4 & 16 & 65536 & 2^{65536} \\ \hline \end{array}$$

Llamaremos $G(n)$ a la inversa de $F$, $G(n) = \min \{ i,~F(i) \ge n \}$. La función $G(n)$ también se llama $\log^* n$, y es la cantidad de veces que debemos tomar logaritmo (base 2 en nuestro caso) a $n$ para que sea $\le 1$. En la práctica, vale $G(n) \le 5$ para cualquier $n$ razonable:

$$\begin{array}{|c|c|c|c|c|c|c|} \hline n & 0--1 & 2 & 3--4 & 5--16 & 17--65536 & 65537--2^{65536} \\ \hline G(n) & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \end{array}$$

Dividiremos a los $n$ nodos en grupos: el nodo $v$ pertenecerá al grupo $g(v) = G(r(v))$. Dicho de otro modo, si observamos el bosque que resulta de aplicar $S'$, los nodos de altura 0 y 1 (hojas y padres de sólo hojas) son del grupo $g=0$, los nodos de altura 2 son del grupo $g=1$, los de altura 3 y 4 son del grupo $g=2$, los de altura 5 a 16 son del grupo $g=3$, etc.

--> imagen

Con estas definiciones ya podemos presentar el análisis amortizado que haremos. Usaremos contabilidad de costos. La operación $Union$ cuesta $O(1)$, por lo que no necesitamos considerarla. Consideraremos que la operación $Find(v)$ cuesta 1 por cada nodo que atravesamos en el camino desde $v$ hasta la raíz $x$. Este costo, para el análisis, lo repartiremos entre la operación Find misma y los nodos que atravesamos, de la siguiente forma:

• Si, al momento de la operación, el nodo es la raíz $x$ de su árbol, o es hijo de la raíz $x$, le cobramos a $Find$.
• Si, al momento de la operación, el nodo tiene distinto grupo que su padre, le cobramos a $Find$.
• De otro modo, le cobramos al nodo por el que pasamos.

--> imagen

Note que, cuando recorremos $v = v_1 \rightarrow \ldots \rightarrow v_r = x$, como cada $v_i$ desciende de $v_{i+1}$, vimos que debe valer $r(v_i) < r(v_{i+1})$, y por lo tanto $g(v_i) \le g(v_{i+1})$. Eso significa que cada vez que el grupo de $v_i$ es distinto del de su padre $v_{i+1}$, el valor del grupo debe aumentar. Como el máximo rango posible es $r = \log_2 n$, los grupos posibles van desde 0 hasta $G(\log_2 n) = G(n)-1$, y entonces en el camino de $v_1$ a $v_r$ el valor del grupo puede aumentar sólo $G(n)-1$ veces. Sumando que $Find$ paga por la raíz $x=v_r$ y su hijo $v_{r-1}$, tenemos que en cada operación nuestra contabilidad de costos le cobra a $Find$ a lo más $1+G(n) = O(\log^* n)$.

Debemos ver ahora cuánto les cobramos a los nodos. Note que, como hemos definido la contabilidad, un nodo que paga adquiere un nuevo padre gracias a la mejora que hace $Find$. Este nuevo padre es un ancestro del padre actual, por lo que su rango es estrictamente mayor. Por lo tanto, cada vez que un nodo paga, adquiere un padre de mayor rango. Una vez que adquiere un padre cuyo rango es de un grupo mayor al del nodo, el nodo no pagará nunca más, pues nunca volverá a tener un padre de su mismo grupo (sólo puede seguir adquiriendo padres de mayor y mayor rango).

¿Cuántas veces puede pagar un nodo hasta adquirir un padre de un grupo superior? Si está en el grupo $g$, y su rango sube sólo de a 1 unidad por vez, puede pagar $F(g)-F(g-1)$ veces hasta que su padre pertenezca al grupo $g+1$. Digamos para simplificar que los nodos de grupo $g$ pueden pagar $F(g)$ unidades en total. ¿Cuántos nodos hay de grupo $g$? Digamos que son $N(g)$, con $N(g) = \sum_{r=F(g-1)+1}^{F(g)} M(r)$, donde hay $M(r)$ nodos de rango $r$. Como vimos que $M(r) \le \frac{n}{2^r}$, tenemos que

$$\begin{array}{c c c } N(g) & \le & \sum_{r=F(g-1)+1}^{F(g)} \frac{n}{2^r} \\ & ~~=~~ & \frac{n}{2^{F(g-1)+1}} \times\!\!\! \sum_{r=0}^{F(g)-F(g-1)-1} \frac{1}{2^r} \\ & ~~<~~ & \frac{2n}{2^{F(g-1)+1}} \\ & ~~=~~ & \frac{n}{2^{F(g-1)}} \\ & ~~=~~ & \frac{n}{F(g)} \end{array}$$

Es decir, tenemos $N(g) \le \frac{n}{F(g)}$ nodos del grupo $g$, y cada uno de ellos paga a lo más $F(g)$ a lo largo de su vida. En total, entre todos los nodos del grupo $g$ pagan a lo más $N(g) \cdot F(g) \le n$. Como existen $G(n)$ grupos distintos, entre todos los nodos pagan $n \cdot G(n)$. Por lo tanto, si se realizan $\Omega(n)$ operaciones de $Find$, el costo amortizado de $Find$ es $O(\log^* n)$, mientras que su costo de peor caso es $O(\log n)$. El costo de los $Union$ es siempre $O(1)$.