ScanImage016 (4)

Ae *sw sm wss ma m< ma WPROWADZENIE

Rysunek 1.8

Zrównoważone szybkie scalanie (przypadek najgorszy)

Najgorszym przypadkiem dla zrównoważonego algorytmu szybkiego scalania jest sytuacja, kiedy operacja scalania dotyczy dwóch drzew o jednakowej wielkości. Jeśli obiektów jest mniej niż 2^k, odległość między dowolnym węzłem i korzeniem jest mniejsza niż k.

3RW Ż5SSS18

szybkim scalaniem z kompresją ścieżek przez połowienie. Która z tych metod jest bardziej efektywna? Czy osiągnięte oszczędności są warte dodatkowego czasu niezbędnego na realizację kompresji ścieżek? Czy istnieje inna technika, którą należy wziąć pod uwagę? Aby odpowiedzieć na te pytania, musimy przyjrzeć się bliżej algorytmom i ich implementacjom. W rozdziale 2 wrócimy do tych zagadnień w kontekście omawiania podstawowego podejścia do analizy algorytmów.

Qstateczny wynik kolejnych analizowanych przez nas mutacji algorytmów rozwiązujących problem połączeniowy możemy uznać za najlepszy, jaki w ogóle w praktyce uda się wymyślić. Mamy algorytmy łatwe do zrealizowania, których czas działania jest zagwarantowany jako liniowo proporcjonalny (stała razy koszt gromadzenia danych). Ponadto algorytmy te działają jednoprzebiegowo (każda krawędź grafu jest rozpatrywana tylko raz), a miejsce zajmowane przez dane jest proporcjonalne do liczby obiektów, nie ma więc ograniczeń co do liczby krawędzi, jakie można zbadać. Wyniki testów empirycznych z tabeli l.l potwierdzają nasz wniosek, że program 1.3 i jego odmiana z kompresją ścieżek nadają się do rozwiązywania nawet dla potężnych zadań praktycznych.

Wskazanie najlepszego spośród przedstawionych algorytmów wymaga dobrze przemyślanej i bardzo zaawansowanej analizy (patrz rozdział 2).

Zadania

♦ 1.4. Pokaż zawartość tablicy id po każdej operacji scalania z algorytmu szybkiego wyszukiwania (programu 1.1) zastosowanego do rozwiązania problemu połączeniowego dla następującej sekwencji par: 0-2. 1-4, 2-5, 3-6, 0-4, 6-0 i 1-3. Podaj liczby wykonywanych przez program dostępów do tablicy id dla każdej wprowadzanej pary.

♦ 1.5. Wykonaj zadanie 1.4, ale użyj algorytmu szybkiego scalania (programu 1.2).

♦ 1.6. Podaj zawartość tablicy id po każdej operacji scalania dla algorytmu zrównoważonego szybkiego scalania uruchomionego dla danych przykładowych z rysunków 1.7 i 1.8.

♦ 1.7. Wykonaj zadanie 1.4, ale użyj algorytmu zrównoważonego szybkiego scalania (programu 1.3).

♦ 1.8. Wykonaj zadanie 1.4, ale użyj algorytmu zrównoważonego szybkiego scalania z kompresją ścieżek przez połowienie (programu 1.4).