W poprzednim wykładzie poznaliśmy kilka podstawowych algorytmów sortowania. Ich wspólną cechą było wykonywanie porównań elementów w celu ustalenia ostatecznej ich kolejności. Inną wspólną cechą tych algorytmów była ich uniwersalność: mogły być stosowane do obiektów dowolnych typów, byle tylko był na nich określony liniowy porządek. Złożoność tych algorytmów wahała się od kwadratowej do liniowo-logarytmicznej względem długości sortowanego ciągu. Teraz zastanowimy się nad złożonością samego problemu sortowania, tzn. zbadamy, jak kosztowne muszą być algorytmy rozwiązywania tego problemu.

Definicja 1.1 Drzewo binarne nazwiemy lokalnie pełnym wtedy i tylko wtedy, gdy każdy wierzchołek tego drzewa jest albo liściem (czyli nie ma następników), albo ma dokładnie dwa następniki.

Niech Sort będzie dowolnym algorytmem rozwiązującym problem sortowania przez porównywanie elementów.

Definicja 1.2 Drzewem decyzyjnym dla algorytmu sortowania Sort zastosowanym do dowolnego n elementowego ciągu, nazywamy etykietowane drzewo binarne, lokalnie pełne, takie że
(1) etykietami wierzchołków wewnętrznych są elementy porównywane w kolejnych krokach algorytmu Sort,
(2) krawędzie "w lewo" odpowiadają odpowiedzi TAK na postawione w wierzchołku pytanie, a krawędzie "w prawo" odpowiadają odpowiedzi NIE,
(3) etykietami liści są uporządkowane niemalejąco permutacje elementów danego ciągu.

Na rysunku 5.1 przedstawiono drzewo decyzyjne algorytmu SelectionSort, zastosowanego do ciągu trzyelementowego e[1], e[2], e[3].

Każde wykonanie algorytmu SelectionSort dla ciągu złożonego z trzech elementów, ma odpowiadającą mu ścieżkę w tym drzewie. Liczby i : j zapisane w wierzchołkach drzewa mówią, że porównywane są elementy i-ty i j-ty sortowanego ciągu. Jeśli e[i] £ e[j], to idziemy w lewo, a w przeciwnym przypadku idziemy w prawo. Liście drzewa zawierają kolejność w jakiej elementy sortowanego ciągu powinny występować w uporządkowaniu niemalejącym. Jeżeli sortowane elementy to e[1] = 3, e[2] = 2, e[3] = 5, to wykonaniu algorytmu SelectionSort dla tego ciągu, odpowiada przejście po ścieżce od korzenia do liścia (2,1,3). J

Na rysunku 5.2 przedstawiono drzewo decyzyjne algorytmu InsertionSort, zastosowanego do ciągu trzyelementowego e[1], e[2], e[3].

Jeżeli sortujemy ciąg e[1] = 2, e[2] = 7, e[3] = 5, to wykonaniu algorytmu InsertionSort odpowiada ścieżka od korzenia do liścia (1,3,2). Zauważmy, że ścieżka odpowiadająca wykonaniu algorytmu InsetionSort dla ciągu e[1] = 3, e[2] = 2, e[3] = 5, jest krótsza niż w przypadku algorytmu SelectionSort. J

Pytanie 1: Ile wierzchołków maksymalnie może się znajdować na poziomie k drzewa decyzyjnego (Korzeń jest na poziomie 0, synowie korzenia - na poziomie 1 itd)?

Lemat 1.1 Jeżeli n jest liczbą liści w drzewie binarnym, a h jego wysokością, to

(a) n £ 2 ^h,(b) h ³ élg nù.

Dowód Lematu 1.1 (a) przeprowadzimy przez indukcję ze względu na h. Oczywiście nierówność (a) jest prawdziwa dla h=0, bo wtedy drzewo składa się tylko z jednego wierzchołka. Załóżmy, że nierówność (a) jest prawdziwa dla wszystkich drzew o wysokości h.

Niech y będzie liczbą wierzchołków wewnętrznych na przedostatnim poziomie tego drzewa. Na mocy założenia indukcyjnego liczbę liści w drzewie do wysokości h możemy oszacować przez 2^h-y. Zatem wszystkich liści w drzewie o wysokości h+1 jest co najwyżej 2y + (2^h-y). Mamy :

Na mocy zasady indukcji matematycznej, nierówność (a) jest prawdziwa dla wszystkich h.

Własność (b) otrzymujemy przez zlogarytmowanie nierówności (a) oraz uwzględnienie faktu, że h jest liczbą naturalną. J

Drzewo decyzyjne dla dowolnego algorytmu sortującego ciąg n elementowy musi zawierać ścieżki prowadzące do wszystkich możliwych odpowiedzi, tzn. wszystkich możliwych permutacji ciągu n elementowego. Wynika stąd, że liczba liści w tym drzewie musi być co najmniej równa n!. Na mocy Lematu 1.1 wysokość h drzewa decyzyjnego dla algorytmu sortującego ciąg n elementowy musi spełniać nierówność h ³ élg n!ù.

Lemat 1.2 Każde drzewo decyzyjne dla dowolnego algorytmu sortującego ciąg n elementowy przez porównywanie elementów, ma co najmniej wysokość élg n!ù.

Wysokość drzewa decyzyjnego wyznacza ograniczenie górne na liczbę wykonanych porównań, na dowolnej ścieżce w drzewie decyzyjnym, a co za tym idzie, determinuje ograniczenie liczby porównań wykonanych przez algorytm sortujący. Wynika stąd następujące twierdzenie:

Twierdzenie 1.3 Każdy algorytm Alg sortujący ciąg n elementowy przez porównania musi wykonać co najmniej élg n!ù porównań w najgorszym przypadku, tzn.

W(Alg, n) ³ élg n!ù.

Przypomnijmy, że lg n! ³ n´lgn - n´lg e. Twierdzenie to mówi, że dla każdego algorytmu sortującego ciąg n elementowy przez porównywanie elementów, zawsze znajdą się takie dane, dla których algorytm musi wykonać co najmniej Q(n´lgn) porównań.

Uwaga. Algorytm MergeSort wykonuje dla dowolnego n elementowego ciągu O(n´lgn) porównań. Jest więc optymalnym algorytmem sortowania, bo górne ograniczenie czasu działania algorytmu jest zgodne z pesymistyczną dolną granicą złożoności problemu.

Pytanie 2: Dla jakich danych algorytm SelectionSort zastosowany do ciągu n elementowego wykonuje co najmniej élg n!ù porównań?