Pytania otagowane jako union-find

1
Ukierunkowane znalezienie związku
Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.GGG Przykład: las rozłączny Rozważ następujący zestaw zapytań: arrow(u, v) equiv(u, v) find(u) pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny reprezentant klasy równoważności ↔ ∗ , tj. r ( …
2
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(logn)O(log⁡n)O(\log n)oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową O(α(n))O(α(n))O(\alpha(n)) (gdzie αα\alphajest odwrotnością funkcji Ackermana). Jednak nie wspomina o czasie działania kompresji ścieżki bez rangi związkowej, co zwykle realizuję sam. Jaka …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.