Komplexität der Vereinigungsfindung mit Pfadkomprimierung ohne Rang

Wikipedia sagt, dass die Vereinigung nach Rang ohne Pfadkomprimierung eine amortisierte Zeitkomplexität von ergibt und dass sowohl die Vereinigung nach Rang als auch die Pfadkomprimierung eine amortisierte Zeitkomplexität von O ( α ( n ) ) ergibt (wobei α die Umkehrung von ist Ackerman-Funktion). Die Laufzeit der Pfadkomprimierung ohne Gewerkschaftsrang wird jedoch nicht erwähnt, was ich normalerweise selbst implementiere.$O(\log n)$$O(\alpha(n))$$\alpha$

Was ist die amortisierte zeitliche Komplexität von Union-Find mit der Pfadkomprimierungsoptimierung, jedoch ohne die Vereinigung durch Rangoptimierung?

$m$$O((m+n)\log(n))$

$f(m,n)$$m$$n$

$k>1$$f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$

$k = \lceil m/n \rceil + 1$

Eine ähnliche Grenze wurde von Tarjan und van Leeuwen in [2], Abschnitt 3, unter Verwendung einer komplexeren Methode angegeben:

$m \geq n$$(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$$(8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil$

$m < n$$n + 2m \lceil \log n\rceil + m$

[1]: R. Seidel und M. Sharir. Top-Down-Analyse der Pfadkomprimierung. Siam J. Computing, 2005, Bd. 34, Nr. 3, S. 515-525.

[2]: R. Tarjan und J. van Leeuwen. Worst-Case-Analyse von Set-Union-Algorithmen. J. ACM. 31, Nr. 2, April 1984, S. 245-281.

$\Theta(n)$

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

$O(\log n)$$O(\log n)$$O(\log n)$ Dies kann in einer interaktiven Anwendung nützlich sein, in der Sie sicherstellen möchten, dass kein einzelner Vorgang eine lange Verzögerung verursachen kann (z. B. möchten Sie die Garantie, dass kein einzelner Vorgang dazu führen kann, dass die Anwendung für eine lange Zeit einfriert) oder in Echtzeit Anwendung, bei der Sie sicherstellen möchten, dass Sie immer die Echtzeitgarantien erfüllen.