Być może, oglądając pucharowe rozgrywki sportowe, zastanawiacie się Państwo, jak to jest, że miejsce drugie zajmują często drużyny, które wcale nie są najlepsze. Doszły do finału i przegrały z mistrzem, ale tak naprawdę reprezentują dużo gorszy poziom od zwycięzcy i  inne drużyny wydają się być dużo lepsze. To nie wydaje się wręcz sprawiedliwe! Jak znaleźć drużynę, która jest obiektywnie najlepsza ze wszystkich, po pominięciu zwycięzcy?

Sformalizujemy problem w następujący sposób: dany jest ciąg n elementów e[1],..., e[n] pewnej liniowo uporządkowanej struktury danych. Znaleźć drugi co do wielkości element tego ciągu, tzn.  znaleźć element największy w zbiorze {e[1],...,e[n]}\max{e[1], ..., e[n]}.  Założymy, że elementy w ciągu nie powtarzają się, i że ciąg posiada co najmniej dwa elementy. Jak zwykle wynik algorytmu zapiszemy na zmiennej result. Przyjmijmy następującą specyfikację:

wp = {e[i] ¹ e[j] dla i¹j, n>0}, 

wk = { result= e[i] dla pewnego i < n+1,  e[j] < result < e[i₀] dla pewnego i₀ i dla wszystkich j ¹ i₀}.

Pierwsza część warunku końcowego, mówi, że wartość zmiennej result jest elementem danego ciągu, a druga część, że tylko jeden element ciągu jest od result większy. Algorytm naiwny, wynikający z samego sformułowania zadania jest następujący:

• 1. Znajdź element największy stosując algorytm max.

• 2. Pomiń w dalszych rozważaniach element największy.

• 3. Wśród pozostałych elementów, znajdź element największy stosując ponownie algorytm max.

Algorytm znajdujący maksimum, max, jest, jak wiadomo, algorytmem optymalnym i wykonuje n-1 porównań dla znalezienia elementu największego (por. wykład I, p.4). Usunięcie elementu maksymalnego może polegać na zamianie pozycji pierwszego i maksymalnego elementu. Koszt tej operacji jest stały. Punkt trzeci algorytmu, można zrealizować szukając elementu największego w ciągu e[2],...,e[n], co wymaga n-2 porównań. Razem koszt algorytmu naiwnego wynosi 2n-3.

Zastanówmy się jednak, czy to drugie wyszukiwanie elementu największego nie mogłoby być zastąpione czymś innym. Czy przeglądając ciąg w poszukiwaniu elementu największego, nie moglibyśmy wykonać części pracy potrzebnej do znalezienia elementu drugiego największego?

Przypatrzmy się jeszcze raz turniejowi rozgrywanemu przez, powiedzmy, n drużyn systemem pucharowym.  W każdym etapie turnieju drużyny grają parami.  Dobór w pary może być losowy. Do następnego etapu przechodzą tylko te drużyny, które wygrywają pojedynki. Oczywiście, po skończonej liczbie rund turniej kończy się wybraniem najlepszej drużyny.

Pytanie 6: Ile rund trzeba wykonać, aby wybrać najlepszą drużynę, jeżeli na początku startowały 32 drużyny?

Ogólnie, jeżeli startowało 2ⁿ drużyn, to  liczba rund wynosi n. A ile dokładnie meczów musiało zostać w tym przypadku rozegranych? 

Wróćmy jednak do problemu bardziej abstrakcyjnego, sformułowanego w specyfikacji powyżej. Każdej drużynie odpowiada teraz jeden element ciągu, a siła drużyny jest wyrażona przez wartość przypisaną temu elementowi. "Mecz" polega na porównaniu dwóch elementów zgodnie z pewną, obwiązującą w przyjętej strukturze danych, relacją porządku liniowego £. "Zwycięża" i przechodzi do następnej rundy element o większej wartości. Oczywiście element, który wygrał w ostatniej rundzie nie przegrał ani jednego "meczu" - jest to rzeczywiście element największy.

Przykład 5.1 Niech elementami ciągu będą liczby naturalne 6, 4 ,9, 8, 5, 7, 3, 1. Przedstawmy w postaci grafu kolejne etapy wyszukiwania elementu największego opisaną metodą, por. Rysunek 3.2.

Węzłami w drzewie turnieju są wartości elementów ciągu. Kolejne rundy turnieju odpowiadają poziomom w tym drzewie. W korzeniu drzewa znajduje się element największy. A gdzie znajduje się element drugi co co wielkości? Nie jest to bynajmniej wierzchołek na na poziomie 1, bo porównywaliśmy tu dziewiątkę z siódemką, a przecież 8 jest większe niż 7. Łatwo zauważyć, że musiał być taki moment, że element największy był porównywany z elementem drugim co do wielkości. W rozważanym przykładzie stało się tak już na początku turnieju, ale mogło się tak stać w dowolnej z rund. Zatem, gdzie szukać drugiego co do wielkości elementu? Wśród elementów, które przegrały z elementem największym.

Obserwacja z przykładu 5.1 jest dostatecznie ogólna, byśmy mogli zaprojektować algorytm rozwiązywania naszego problemu. Zapiszemy go nieformalnie, implementację przedstawionej tu metody omówimy później w wykładzie szóstym.

Zauważmy najpierw, że koszt tego algorytmu jest dużo mniejszy niż algorytmu naiwnego. Znalezienie elementu największego wiąże się z wykonaniem n-1 porównań niezależnie od tego, czy liczba n jest, czy nie jest potęgą dwójki. Elementy, które nie miały pary, przechodzą do następnego etapu, bez wykonywania porównań. Liczba rund turnieju wynosi élg nù, bo jest to wysokość drzewa binarnego o n liściach, por. wykład II, p.5. Zatem ciąg, który musimy ponownie przeszukać składa się z élg nù  elementów. Ostatecznie liczba wykonanych porównań wynosi n-1 + élg nù-1,

T(Turniej, n) = n + élg nù-2 .

Cała trudność w implementacji tego algorytmu polega za sposobie znalezienia elementów, które przegrały ze zwycięzcą, tak by nie wykonywać żadnych dodatkowych porównań elementów. Ponieważ budując drzewo turnieju nie wiemy, który element zwycięży, zatem dla każdego wygrywającego trzeba pamiętać listę elementów, które z nim przegrały. Implementację wykorzystującą strukturę list i strukturę stosów omówimy w rozdziale szóstym.

Pytanie 7: Ile dokładnie porównań wykona algorytm Turniej dla ciągu dziewięcioelementowego, jeżeli założymy, że element, który nie ma pary automatycznie przechodzi do następnej rundy? 

« poprzedni punkt

następny punkt »