Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową (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?
complexity-theory
time-complexity
union-find
Filip Haglund
źródło
źródło
Odpowiedzi:
Seidel i Sharir udowodnili w 2005 r. [1], że z grubsza korzystają z kompresji ścieżki z arbitralnym łączeniemm operacje mają z grubsza złożoność O ( ( m + n ) log( n ) ) .
Patrz [1], sekcja 3 (Arbitrary Linking): Letfa( m , n ) oznacza środowisko wykonawcze union-find with m operacje i n elementy. Udowodniono, że:
Zgodnie z [1] ustawieniek=⌈m/n⌉+1 daje
f(m,n)≤(2m+n)log⌈m/n⌉+1n .
Podobną granicę podał stosując bardziej złożoną metodę Tarjan i van Leeuwen w [2], Rozdział 3:
[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.
źródło
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.
źródło