ScanImage012 (5)

i żm KttK MK BBS WPROWADZENIE

Program 1.2. Rozwiązanie problemu połączeniowego.

Algorytm szybkiego scalania

Jeżeli zastąpić treść pętli while z programu 1.1 poniższym kodem, można otrzymać program zgodny z tą samą specyfikacją co program 1.1, ale wykonujący mniej obliczeń podczas operacji scalania kosztem większej liczby obliczeń w operacji wyszukiwania. Pętle for i występująca po nich instrukcja i f służą do wyznaczania na podstawie tablicy id koniecznych i dostatecznych warunków istnienia połączenia między p i q. Przypisanie id [ i J = j to realizacja operacji scalania.

for (i=p; i != id[ij; i=id[i]); for <j=q; j !» idfjl; j=id[j]); if (i =" j) continue;

id r i 1=j;

cout « " " « p « " " « ą « endl;

-------i

Program 1.2 stanowi rozwiązanie problemu połączeniowego oparte na algorytmie szybkiego scalania. Algorytm ten może wydawać się szybszy niż poprzedni, ponieważ nie wymaga przeglądania całej tablicy dla każdej wprowadzanej na wejściu pary, ale o ile szybszy? Na to pytanie trudniej odpowiedzieć niż na pytanie o wydajność algorytmu szybkiego wyszukiwania, ponieważ czas działania tego programu jest bardziej zależny od natur)' wprowadzanych danych. Na podstawie testów empirycznych i przeprowadzonych analiz matematycznych (patrz rozdział 2), możemy stwierdzić, że program 1.2 jest dalece bardziej wydajny niż program 1.1 i że można go stosować do rozwiązywania potężnych zadań praktycznych. Jeden z takich testów empirycznych zostanie omówiony pod koniec tego podrozdziału. Na razie możemy przyjąć, że algorytm szybkiego scalania jest szybszy, bo usuwa główną wadę poprzedniego (to, iż program wymaga przynajmniej n m instrukcji do przeprowadzenia m operacji scalania na n obiektach).

Przejście z algorytmu szybkiego wyszukiwania do algorytmu szybkiego scalania jest w istocie skokiem jakościowym, ale nasze poszukiwania jeszcze się nie zakończyły, ponieważ ten drugi nic jest wciąż pozbawiony wad. Ma on mianowicie taką niedogodność, że nic możemy zagwarantować, iż będzie on znacząco szybszy w każdym przypadku, ponieważ jego wydajność zależy od natury danych wejściowych, mogących przy niekorzystnym układzie spowalniać jego działanie.

Twierdzenie 1.2. Dla nt > n rozwiązanie problemu połączeniowego za pomocą algorytmu szybkiego scalania może wymagać wykonania więcej niż rnn/2 instrukcji, gdzie m to liczba par, a n liczba obiektów.

Załóżmy, że pary wejściowa pojawuająsię w następującej kolejności: 1-2, 2-3, 3-4 itd. Po n - 1 takich parach mamy n obiektów, z których każdy należy do tego samego zbioru, oraz drzewo utworzone przez algorytm szybkiego scalania w postaci linii prostej, przy czym obiekt n wskazuje na n - 1, który wskazuje na n - 2, który wskazuje na n - 3 itd. Aby przeprowadzić operację wyszukiwania dla obiektu n, program musi przejść przez n - 1 wskaźników. Dlatego też średnia liczba wskaźników' przeskoczonych dla pierwszych n par wynosi: