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

10

Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu O(logn)oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową O(α(n)) (gdzie α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?

Filip Haglund
źródło
5
Zauważ, że α(n) jest odwrotnością funkcji Ackermana, a nie 1/ZA(n,n)). Tutaj „odwrotność” oznacza odwrotność jako funkcję, a nie odwrotność: tzn. Jeślifa(n)=ZA(n,n), α(n)=f1(n), nie 1/f(n).
DW
Rozumiem, że jest to stosunkowo stare pytanie, ale zobacz moją odpowiedź i odpowiedni artykuł: epubs.siam.org/doi/abs/10.1137/S0097539703439088 . Mogłem przeoczyć jakiś szczegół lub dwa podczas kopiowania poza granice. W takim przypadku zaproponuj edycję :-)
BearAqua

Odpowiedzi:

4

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 fa(m,n) oznacza środowisko wykonawcze union-find with m operacje i nelementy. Udowodniono, że:

Roszczenie 3.1. Dla dowolnej liczby całkowitejk>1 mamy f(m,n)(m+(k1)n)logk(n).

Zgodnie z [1] ustawienie k=m/n+1 daje

f(m,n)(2m+n)logm/n+1n
.

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

Lemat 7 z [2]. Przypuszczaćmn. 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)log1+m/nn Przy zmniejszeniu o połowę i naiwnym łączeniu całkowita liczba węzłów na ścieżkach wyszukiwania wynosi co najwyżej (8m+2)n)log1+m/n(n).

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żejn+2)mlogn+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.

BearAqua
źródło
2

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 Θ(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Θ(n)czas. Zatem najgorszy możliwy czas działania przypada na jedną operacjęΘ(n).

W przeciwieństwie do optymalizacji łączenia według rang, najgorszy możliwy jest czas działania na operację O(logn): żadna operacja nie może trwać dłużej niż O(logn). 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ę doO(logn) 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.

DW
źródło