Complejidad de union-find con path-compresión, sin rango

Wikipedia dice que la unión por rango sin compresión de ruta da una complejidad de tiempo amortizada de , y que tanto la unión por rango como la compresión de ruta da una complejidad de tiempo amortizada de O ( α ( n ) ) (donde α es el inverso de Función Ackerman). Sin embargo, no menciona el tiempo de ejecución de la compresión de ruta sin rango de unión, que es lo que generalmente implemento yo mismo.$O(\log n)$$O(\alpha(n))$$\alpha$

¿Cuál es la complejidad del tiempo amortizado de union-find con la optimización de compresión de ruta, pero sin la unión por optimización de rango?

Seidel y Sharir demostraron en 2005 [1] que usar la compresión de ruta con enlaces arbitrarios aproximadamente en $m$ operaciones tiene una complejidad de aproximadamente $O((m+n)\log(n))$ .

Ver [1], Sección 3 (Enlace Arbitrario): Sea $f(m,n)$ el tiempo de ejecución de union-find con $m$ operaciones $n$ elementos. Probaron lo siguiente:

Reclamación 3.1. Para cualquier entero $k>1$ tenemos $f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$ .

De acuerdo con [1], la configuración de $k = \lceil m/n \rceil + 1$ da

Tarjan y van Leeuwen dieron un enlace similar usando un método más complejo en [2], Sección 3:

Lema 7 de [2]. Supongamos que $m \geq n$ . En cualquier secuencia de operaciones de conjuntos implementadas utilizando cualquier forma de compactación y enlace ingenuo, el número total de nodos en las rutas de búsqueda es a lo sumo $(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$ Con enlace a la mitad e ingenuo, el número total de nodos en las rutas de búsqueda es como máximo $(8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil$ .

Lema 9 de [2]. Supongamos que $m < n$ . En cualquier secuencia de operaciones de conjuntos implementadas usando compresión y enlaces ingenuos, el número total de nodos en las rutas de búsqueda es como máximo $n + 2m \lceil \log n\rceil + m$ .

[1]: R. Seidel y M. Sharir. Análisis de arriba hacia abajo de la compresión del camino. Siam J. Computing, 2005, vol. 34, núm. 3, págs. 515-525.

[2]: R. Tarjan y J. van Leeuwen. Análisis de los peores casos de algoritmos de unión de conjuntos. J. ACM, vol. 31, núm. 2, abril de 1984, págs. 245-281.

$\Theta(n)$

$n$$n-1$$\Theta(n)$$\Theta(n)$

$O(\log n)$$O(\log n)$$O(\log n)$ puede ser útil en una aplicación interactiva en la que desea asegurarse de que ninguna operación individual puede causar un retraso prolongado (por ejemplo, desea una garantía de que ninguna operación individual puede hacer que la aplicación se congele durante mucho tiempo) o en tiempo real aplicación en la que desea asegurarse de cumplir siempre con las garantías en tiempo real.