Algorytmy i struktury danych · Senior · Pytanie 6 z 75
Co sprawia, że operacje union-find są prawie O(1)?
- 1Trzymanie każdego zbioru jako posortowanej tablicy
- ✓Poprawna odpowiedź: Kompresja ścieżek plus łączenie według rangi lub rozmiaru
- 3Przebudowa całej struktury po każdym połączeniu
Wyjaśnienie
Kompresja ścieżek podczas find kieruje węzły wprost na korzeń; łączenie według rangi podpina niższe drzewo pod wyższe. Razem dają zamortyzowane O(α(n)), gdzie α (odwrotna funkcja Ackermanna) jest mniejsza niż 5 dla każdego realnego n.