2. Złożoność problemu sortowania, koszt średni.

W tym punkcie zbadamy ograniczenie dolne na liczbę porównań wykonywanych w procesie sortowania, w przypadku średnim. Zadanie polega na zbadaniu średniej długości ścieżki w drzewie decyzyjnym dla algorytmów sortujących przez porównywanie elementów.

Niech D będzie drzewem binarnym, L zbiorem jego liści, a p(v) - długością ścieżki od korzenia do liścia v w drzewie D. Przyjmijmy też następujące oznaczenie:

epl(D) jest po prostu sumą długości wszystkich ścieżek od korzenia do liści w drzewie D.

Lemat 2.1 Jeżeli dla pewnego D wartość epl(D) jest najmniejsza wśród drzew binarnych lokalnie pełnych o n liściach, to wszystkie liście tego drzewa D znajdują się na dwóch ostatnich poziomach.

Załóżmy przeciwnie, że w drzewie D_n o n liściach i wysokości h, istnieje liść u na poziomie k, k £ h-2, a mimo to wartość epl(D_n) jest minimalna wśród wszystkich drzew binarnych lokalnie pełnych o n liściach (por. Rysunek 5.4).

Niech w będzie wierzchołkiem na poziomie h-1, a w₁ i w₂ niech będą jego następnikami. Co najmniej jeden taki wierzchołek istnieje, bo drzewo D ma wysokość h. Zbudujemy nowe drzewo D*przenosząc liście w₁, w₂ z ostatniego poziomu i dowiązując je jako synów wierzchołka u.

Taka modyfikacja nie zmieniła liczby liści w drzewie, zatem D* ma też n liści i jest drzewem lokalnie pełnym. Mamy

ponieważ w jest w D* liściem, a u nie jest, oraz w₁, w₂znajdują się teraz nie na poziomie h, a na poziomie k+1. Stąd

Ponieważ z założenia k < h-1, zatem epl(D*) < epl(D_n). Otrzymaliśmy sprzeczność, która dowodzi prawdziwości lematu 2.1. J

Jaka jest wartość sumy długości ścieżek w lokalnie pełnym drzewie binarnym o n liściach? Jeśli D jest to pełnym drzewem binarnym, to wszystkie ścieżki mają taką samą długość, równą lg n, a wtedy epl(D)= n´lg n. W dalszym ciągu rozważymy dowolne drzewa rodziny D(n) drzew binarnych, lokalnie pełnych, o n liściach. Udowodnimy następujące ograniczenie dolne wartości epl dla drzew tej rodziny.

Lemat 2.2 min{epl(D): DÎ D(n)} = n ëlg nû + 2( n - 2^{ëlg n}^û).

Niech D będzie drzewem z rodziny D(n), oraz niech wartość funkcji epl dla tego drzewa osiąga minimum. Na mocy lematu 2.1 wiemy, że wszystkie liście w tym drzewie znajdują się na dwóch ostatnich poziomach. Rozważmy dwa przypadki.

1. n= 2^p dla pewnego p. Wtedy mamy do czynienia z pełnym drzewem binarnym, wszystkie liście znajdują się na poziomie p i oczywiście epl(D)= n lg n = n ëlg nû + 2( n - 2^{ëlg n}^û). Zatem w tym przypadku lemat 2.2 jest prawdziwy.

2. 2^p-1 < n < 2^p, dla pewnego p. Na mocy lematu 1.1, h ³ élg nù. Gdyby jednak h > élg nù, to licząc liczbę liści w tym drzewie przy założeniu, że na przedostatnim poziomie jest y nie-liści, otrzymalibyśmy sprzeczność z założeniem:

((2 ^h-1 - y)- to liście na przedostatnim poziomie, a 2y - to liście na ostatnim poziomie). Zatem, dla drzewa D w rozważanym przypadku musi być h = élg nù. Policzmy wartość funkcji epl(D):

Ponieważ n = 2y + (2 ^h-1 - y) , to y = n - 2 ^h-1 . Stąd , biorąc pod uwagę równość ëlg nû +1 = élg nù, otrzymujemy:

epl(D) = h ´ n - 2^h + n = n élg nù - 2 ^{élg nù} + n = n ëlg nû + 2( n - 2^{ëlg n}^û). J

Lemat 2.3 Średnia liczba porównań wykonanych przez dowolny algorytm Alg sortujący ciąg n elementowy przez porównania, jest nie mniejsza niż ëlg n!û, A(Alg, n) ³ ëlg n!û.

Średnia wysokość h drzewa decyzyjnego wynosi, na mocy lematu 2.2, co najmniej

Ponieważ dla dowolnego x, x/2 £ 2^{ëlg x}^û £ x, zatem (2^{ëlg x}^û / x) £ 1, a co za tym idzie 2(n! - 2^{ëlg n!}^û)/ n! ³ 0. Ostatecznie

Twierdzenie 2.1 Dolne ograniczenie złożoności algorytmów sortowania przez porównywanie elementów wynosi w przypadku średnim Q(n´lg n).

Wniosek: Algorytm QuickSort jest asymptotycznie optymalnym algorytmem sortowania ze względu na średnią złożoność czasową.

Pytanie 3: Czy MergeSort jest algorytmem asymptotycznie optymalnym ze względu na średnią złożoność czasową?