Złożoność znalezienia związku z kompresją ścieżki, bez rangi

Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu $O(\log n)$oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową $O(\alpha(n))$ (gdzie $\alpha$jest odwrotnością funkcji Ackermana). Jednak nie wspomina o czasie działania kompresji ścieżki bez rangi związkowej, co zwykle realizuję sam.

Jaka jest zamortyzowana złożoność czasowa znalezienia związku z optymalizacją kompresji ścieżki, ale bez połączenia według optymalizacji rang?

Seidel i Sharir udowodnili w 2005 r. [1], że z grubsza korzystają z kompresji ścieżki z arbitralnym łączeniem $m$ operacje mają z grubsza złożoność $O((m+n)\log(n))$.

Patrz [1], sekcja 3 (Arbitrary Linking): Let $f(m,n)$ oznacza środowisko wykonawcze union-find with $m$ operacje i $n$elementy. Udowodniono, że:

Roszczenie 3.1. Dla dowolnej liczby całkowitej$k>1$ mamy $f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$.

Zgodnie z [1] ustawienie $k = \lceil m/n \rceil + 1$ daje

Podobną granicę podał stosując bardziej złożoną metodę Tarjan i van Leeuwen w [2], Rozdział 3:

Lemat 7 z [2]. Przypuszczać$m \geq n$. W dowolnej sekwencji zestawów operacji realizowanych przy użyciu dowolnej formy zagęszczania i naiwnego łączenia całkowita liczba węzłów na ścieżkach wyszukiwania wynosi co najwyżej$(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$ Przy zmniejszeniu o połowę i naiwnym łączeniu całkowita liczba węzłów na ścieżkach wyszukiwania wynosi co najwyżej $(8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil$.

Lemat 9 z [2]. Przypuszczać$m < n$. W dowolnej sekwencji operacji ustawiania realizowanych przy użyciu kompresji i naiwnego łączenia całkowita liczba węzłów na ścieżkach wyszukiwania wynosi co najwyżej$n + 2m \lceil \log n\rceil + m$.

[1]: R. Seidel i M. Sharir. Analiza z góry na dół kompresji ścieżki. Siam J. Computing, 2005, tom. 34, nr 3, str. 515–525.

[2]: R. Tarjan i J. van Leeuwen. Analiza najgorszego przypadku zestawu algorytmów unii. J. ACM, tom. 31, nr 2, kwiecień 1984, s. 245–281.

Nie wiem, jaki jest zamortyzowany czas działania, ale mogę przytoczyć jeden z możliwych powodów, dla których w niektórych sytuacjach możesz chcieć używać obu zamiast kompresji ścieżki: najgorszy przypadek czasu na operację to $\Theta(n)$ jeśli użyjesz tylko kompresji ścieżki, która jest znacznie większa niż jeśli użyjesz zarówno łączenia według rangi, jak i kompresji ścieżki.

Rozważ sekwencję $n$ Operacje unijne złośliwie wybrane w celu uzyskania drzewa głębi $n-1$(jest to tylko sekwencyjna ścieżka węzłów, gdzie każdy węzeł jest dzieckiem poprzedniego węzła). Następnie wykonanie pojedynczej operacji Znajdź w najgłębszym węźle zajmuje$\Theta(n)$czas. Zatem najgorszy możliwy czas działania przypada na jedną operację$\Theta(n)$.

W przeciwieństwie do optymalizacji łączenia według rang, najgorszy możliwy jest czas działania na operację $O(\log n)$: żadna operacja nie może trwać dłużej niż $O(\log n)$. W przypadku wielu aplikacji nie będzie to miało znaczenia: liczy się tylko całkowity czas działania wszystkich operacji (tj. Zamortyzowany czas działania), a nie najgorszy czas dla pojedynczej operacji. Jednak w niektórych przypadkach najgorszy przypadek na operację może mieć znaczenie: na przykład skrócenie najgorszego przypadku na operację do$O(\log n)$ może być przydatny w interaktywnej aplikacji, w której chcesz się upewnić, że żadna pojedyncza operacja nie może spowodować dużego opóźnienia (np. chcesz mieć gwarancję, że żadna pojedyncza operacja nie spowoduje zawieszenia aplikacji na długi czas) lub w czasie rzeczywistym aplikacja, w której chcesz mieć pewność, że zawsze będziesz spełniać gwarancje w czasie rzeczywistym.