ScanImage014 (5)

on sssss xxs mm    sm

WPROWADZENIE

(5) <D & (5) (fi) (fi) © <D ® <S) <3) ® (fi) (fi) ® ®

Rysunek 1.7 Drzewowa reprezentacja zrównoważonego szybkiego scalania

Ta sekwencja ilustruje wynik zmiany algorytmu szybkiego scalania polegającej na przyłączaniu korzenia mniejszego drzewa do korzenia drzewa większego. Odległość od dowolnego węzła do korzenia w jego drzewie jest mała. więc operacja wyszukiwania działa szybciej.

Możemy dowieść, że operacja scalania ma taką własność, iż liczba wskaźników napotkanych na drodze od dowolnego węzła do korzenia drzewa zbudowanego zc zbioru k obiektów nie jest większa niż Ig k. Kiedy połączymy zbiór i węzłów ze zbiorem j węzłów, przy czym i < j. zwiększamy o 1 liczbę wskaźników, które trzeba przejść dla elementów ze zbioru mniejszego, ale teraz są one w zbiorze o wielkości i + y, więc twierdzenie jest spełnione, ponieważ 1 + lg / = lg (i + i) < Ig (/ + y).    ■

Praktyczne implikacje twierdzenia 1.3 polegają na tym, że zrównoważony algorytm szybkiego scalania wymaga wykonania najwyżej cm Ig n instrukcji, gdzie m - liczba krawędzi, n - liczba obiektów', c stała (patrz zadanie 1.9). Wynik ten znacząco odbiega od tego, że algorytm szybkiego wyszukiwania w^fymaga zawsze (a szybkiego scalania - czasem) przynajmniej m n/2 instrukcji. Wniosek jest taki, że algorytm zrówmoważonego szybkiego scalania może zagwarantować rozwiązywanie w rozsądnym czasie praktycznych zadań o wielkim rozmiarze (patrz zadanie 1.11). Za cenę kilku dodatkowych linii kodu otrzymujemy program, który w przypadku ogromnych zadań, a z takimi spotykamy się w zastosowaniach praktycznych, jest miliony razy szybszy niż algorytmy prostsze.

Na podstawie diagramów widać, że relatywoiic mała liczba węzłów znajduje się daleko od korzenia. Jak pokazują testy' empiryczne przeprowadzone na ogromnej liczbie danych, algorytm zrównoważonego szybkiego scalania (program 1.3) pozwala z reguły na rozwiązanie rzeczywistych zadań w czasie liniowym. Oznacza to, że koszt działania algorytmu jest rówmy iloczynowi stałej i kosztu odczytania danych wejściowych. Znalezienie bardziej efektywnego algorytmu jest mało prawdopodobne.

Natychmiast nasuwa się pytanie, czy można znaleźć algorytm, który zagwarantowałby wydajność liniową. Jest to niezwykle trudna kwestia, która spędza sen z powiek naukowcom od wielu lat (patrz podrozdział 2.7). Istnieje kilka prostych sposobów dalszego poprawienia wydajności algorytmu zrównoważonego szybkiego scalania. W idealnym przypadku każdy węzeł powinien wskazywać bezpośrednio na korzeń jego drzewa, ale nie chcemy ponosić kosztu zmian dużej liczby wska-