Analiza szybkiego sortowania

Jak to się dzieje, że czas wykonania w przypadku najlepszego i typowego scenariusza jest różny? Zacznijmy od przyjrzenia się czasowi wykonania najgorszego scenariusza. Przypuśćmy, że naprawdę mieliśmy pecha i podziały są znacząco niezrównoważone. W szczególności, załóżmy, że element rozdzielający wybrany przez funkcję dzielącą jest zawsze najmniejszym lub największym elementem $n$‍-elementowej podtablicy. Wtedy jeden z podziałów nie zawiera żadnych elementów, podczas, gdy drugi zawiera $n-1$‍ elementów - wszystkie, oprócz elementu rozdzielającego. Na skutek tego wywołania rekursywne będą działać na podtablicach o rozmiarach 0 i $n-1$‍ elementów.

Tak jak w sortowaniu przez scalanie, czas na określone wywołanie rekursywne na $n$‍-elementowej podtablicy wynosi $\mathrm{\Theta }(n)$‍. W sortowaniu przez scalanie czas ten był przeznaczony na scalanie, podczas, gdy w sortowaniu szybkim to czas na podział.

W sortowaniu szybkim najbardziej niezrównoważone podziały są zawsze możliwe. W takim przypadku oryginalne wywołanie zajmuje $cn$‍ porównań, dla pewnej stałej $c$‍, wywołanie rekursywne na $n-1$‍ elementów wymaga $c(n-1)$‍ porównań, wywołanie rekursywne na $n-2$‍ elementów wymaga $c(n-2)$‍ porównań itd. Poniżej przedstawiono drzewo rozmiarów podproblemów z ich ilością podziałów:

Gdy podsumujemy ilość podziałów dla każdego poziomu, otrzymamy

Ostatnie wyrażenie wynika z faktu, że $1+2+3+\cdots +n$‍ jest ciągiem artymetycznym, co widzieliśmy gdy analizowaliśmy sortowanie przez wybieranie. (Odejmujemy 1 ponieważ, w przypadku sortowania szybkiego, sumowanie rozpoczyna się od 2, a nie od 1). Mamy pewne wyrażenia niskiego stopnia oraz stałe współczyniki, ale gdy używamy notacji dużego-O, ignorujemy je. W notacji dużego-O, czas wykonywania w najgorszym przypadku wynosi $\mathrm{\Theta }(n^2)$‍

Najlepszy przypadek szybkiego sortowania występuje, gdy podziały są możliwie równe: ich rozmiary są równe albo różnią się jednym elementem. Pierwszy przypadek występuje, jeśli podtablica ma nieparzystą liczbę elementów i element rozdzielający znajduje się dokładnie w środku po podziale i każdy podział ma $(n-1)/2$‍ elementów. Drugi przypadek występuje, jeśli podtablica ma parzystą liczbę $n$‍ elementów i jeden podział ma $n/2$‍, a drugi$$‍ n/2-1 elementów. W tych przypadkach każdy podział ma najwyżej $n/2$‍ elementy, i drzewo rozmiarów podproblemów wygląda jak drzewo rozmiarów podproblemów dla sortowania przez scalanie, z czasami podziału wyglądającymi jak czasy łączenia:

Jeśli zastosujemy notację duże-Θ, otrzymamy wynik identyczny jak w przypadku sortowania przez scalanie: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

Pokazanie, że czas wykonania typowego sortowania wynosi również $\mathrm{\Theta }(n{\log }_{2}n)$‍ wymaga dość zaawansowanej matematyki, zatem nie będziemy się w to zagłębiać. Natomiast możemy spróbować zrozumieć, dlaczego jest to $O(n{\log }_{2}n)$‍, patrząc na kilka innych przypadków. (Skoro mamy $O(n{\log }_{2}n)$‍, wynika z tego oszacowanie $\mathrm{\Theta }(n{\log }_{2}n)$‍, ponieważ czas wykonania w typowym przypadku nie może być lepszy, niż czas wykonania w najkorzystniejszej sytuacji. Załóżmy po pierwsze, że nie zawsze otrzymujemy zrównoważone podziały, ale zawsze, w najgorszym razie mamy podział 3:1. Tzn., załóżmy, że przy każdym podziale, jeden podciąg otrzymuje $3n/4$‍, a drugi $n/4$‍ elementów. (Aby uprościć wyliczenia, nie bierzemy pod uwagę elementu rozdzielającego). W tym przypadku drzewo podproblemów oraz czasy podziałów wyglądałyby następująco:

Lewy potomek każdego węzła reprezentuje podproblem o 1/4, zaś prawy potomek o 3/4 wielkości. Ponieważ mniejsze podproblemy są po lewej, idąc ścieżką lewych potomków, docieramy od korzenia do podproblemu o rozmiarze 1 szybciej, niż jakąkolwiek inną ścieżką. Jak pokazuje ilustracja, po ${\log }_{4}n$‍ poziomach docieramy do podproblemu o rozmiarze 1. Dlaczego ${\log }_{4}n$‍ poziomów? Najłatwiej rozważyć tą kwestię rozpoczynając od podproblemu o rozmiarze 1 i mnożąc je przez 4, aż do osiągnięcia $n$‍. Innymi słowy, pytamy jaka wartość $x$‍ spełnia równanie $4^x=n$‍? Odpowiedzią jest ${\log }_{4}n$‍. A co gdybyśmy wybrali ścieżkę prawych potomków? Ilustracja pokazuje, że zajmuje to ${\log }_{4/3}n$‍ poziomów, aby dotrzeć do podproblemu rozmiaru 1. Dlaczego ${\log }_{4/3}n$‍ poziomów? Ponieważ każdy prawy potomek stanowi 3/4 rozmiaru węzła powyżej niego (jego węzeła rodzicielskiego ), każdy rodzic ma 4/3 rozmiaru swojego prawego potomka. Pponownie rozważymy rozpoczęcie od podproblemu o rozmiarze 1 i mnożenie przez 4/3, aż osiągniemy $n$‍. Dla jakiej wartości $x$‍ spełnione jest równanie $(4/3{)}^x=n$‍? Odpowiedzią jest ${\log }_{4/3}n$‍.

W każdym z pierwszych ${\log }_{4}n$‍ poziomów, znajduje się $n$‍ węzłów (ponownie, włączając w to elementy rozdzielające, które w rzeczywistości nie podlegają podziałowi), a zatem całkowity czas podziału dla każdego z tych poziomów wynosi $cn$‍. Ale co z resztą poziomów? Każdy z nich ma mniej niż n węzłów i czas podziału dla każdego z poziomów wynosi co najwyżej $cn$‍. Razem, mamy ${\log }_{4/3}n$‍ poziomów, więc całkowity czas podziału wynosi $O(n{\log }_{4/3})$‍. Istnieje zależność

dla wszystkich liczb dodatnich $a$‍, $b$‍, i $n$‍. Podstawiając $a=4/3$‍ i $b=2$‍, otrzymujemy

tak więc ${\log }_{4/3}n$‍ oraz ${\log }_{2}n$‍ różnią się jedynie czynnikiem ${\log }_2(4/3)$‍,który jest stały. Ponieważ stałe nie są brane pod uwagę w notacji dużego-O, możemy powiedzieć, że w przypadku gdy wszystkie podziały są w stosunku 3-do-1, złożoność obliczeniowa wykonania algorytmu quicksort wynosi $O(n{\log }_{2}n)$‍, aczkolwiek z większym ukrytym czynnikiem stałym niż w najlepszym przypadku.

Jak często możemy oczekiwać podziału 3:1 lub lepszego? To zależy od tego, jak wybieramy element rozdzielający. Wyobraźmy sobie, że istnieje jednakowo równe prawdopodobieństwo wystąpienia elementu rozdzielającego w dowolny miejscu $n$‍-elementowej podtablicy po podziale. Wtedy, aby uzyskać podział 3:1 lub lepszy, element rodzielający musiałby znajdować się w "środkowej połowie":

Zatem, jeśli element rozdzielający ma równe prawdopodobieństwo wystąpienia w dowolnym miejscu podciągu po podziale, istnieje 50% szansa otrzymania podziału przynajmniej 3:1. Innymi słowy, oczekujemy podziału 3:1 lub lepszego w około połowie przypadków.

Aby zrozumieć, dlaczego typowy czas wykonania szybkiego sortowania wynosi $O(n{\log }_{2}n)$‍, przyjrzymy się przypadkowi, gdy nie otrzymujemy w połowie przypadków podziału 3:1, a podział jak w najgorszym przypadku. Załóżmy, że przypadki podziału 3:1 oraz podziału jak w najgorszym przypadku występują naprzemiennie, i rozważmy węzeł drzewa z $k$‍-elementami w jego podciągu. Zobaczylibyśmy wtedy część drzewa wyglądającą następująco:

zamiast takiego:

Dlatego też, nawet jeżeli uzyskamy podział najgorszego przypadku w połowie czasu i podział 3:1 lub lepszy w drugiej połowie, czas wykonania będzie około dwukrotnie większy niż czas wykonania przy podziale 3:1 przez cały czas. Niemniej, jest to czynnik stały, uwzględniony w notacji dużego-O i w tym przypadku, gdzie naprzemiennie stosujemy podziały najgorszego przypadku i 3:1, czas wykonania wynosi $O(n{\log }_{2}n)$‍

Miej na uwadze, że ta analiza _nie_jestmatematycznie ścisła, ale daje intuicyjny wgląd, że czas wykonywania średniego przypadku może być $O(n{\log }_{2}n)$‍.

Załóżmy że Twój najgorszy wróg dał Ci tablicę do posortowania za pomocą algorytmu quicksort i wiedząc że za każdym razem jako element rozdzielający wybierasz element najbardziej po prawej skonstruował tę tablicę w taki sposób że zawsze będziesz miał do czynienia z najgorszym przypadkiem. W jaki sposób możesz pokonać swojego wroga?

Niekoniecznie musimy wybierać prawy, skrajny element każdej podtablicy jako element rozdzielający. Zamiast tego, możemy losowo wybrać element w podtablicy i użyć go jako element rozdzielający. Ale chwileczkę - funkcja dzieląca zakłada, że element rozdzielący jest prawym, skrajnym elementem w każdej podtablicy. Nie ma problemu - wystarczy zamienić wybrany element rozdzielający z prawym, skrajnym elementem i dzielić jak poprzednio. I jeśli twój wróg nie wie jak wybierasz losowe położenia w podtablicy, wygrywasz!

W rzeczywistości, przy niewielkim wysiłku, możemy powiększyć szansę otrzymania podziału, który w najgorszym przypadku jest 3:1. Wybieramy losowo nie jeden, ale trzy elementy z podtablicy, i bierzemy medianę z trzech jako element rozdzielający (zamieniając z elementem prawym, skrajnym). Poprzez medianę rozumiemy element o wartości środkowej z trzech. Nie pokażemy dlaczego, ale jeśli wybierzemy medianę z trzech losowo wybranych elementów jako element rozdzielający, mamy 66,75% (11/16) szansę otrzymania podziału 3:1 lub lepszego. Możemy pójść nawet dalej. Jeśli wybierzemy 5 losowych elementów i obierzemy ich medianę jako element rozdzielający, szansa otrzymania podziału 3:1 w najgorszym przypadki poprawia się do około 79,3% (203/256). Jeśli wybierzemy medianę z siedmiu losowo wybranych elementów, szansa wzrasta do około 85,9% (1759/2048). Mediana z dziewięciu? Około 90,2% (59123/65536). Mediana z 11? Około 93,1% (488293/524288). Zależność jest widoczna. Oczywiście, niekoniecznie opłaca się wybierać dużej liczby losowych elementów i wybieranie ich mediany, jako, że czas spędzany na tej operacji może przeważyć korzyści uzyskane z otrzymania dobrych podziałów w większości czasu.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.