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$n-elementowej podtablicy. Wtedy jeden z podziałów nie zawiera żadnych elementów, podczas, gdy drugi zawiera $n-1$n, minus, 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$n, minus, 1 elementów.

Tak jak w sortowaniu przez scalanie, czas na określone wywołanie rekursywne na $n$n-elementowej podtablicy wynosi $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. 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$c, n porównań, dla pewnej stałej $c$c, wywołanie rekursywne na $n-1$n, minus, 1 elementów wymaga $c(n-1)$c, left parenthesis, n, minus, 1, right parenthesis porównań, wywołanie rekursywne na $n-2$n, minus, 2 elementów wymaga $c(n-2)$c, left parenthesis, n, minus, 2, right parenthesis 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$1, plus, 2, plus, 3, plus, \@cdots, plus, 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 $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis

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$left parenthesis, n, minus, 1, right parenthesis, slash, 2 elementów. Drugi przypadek występuje, jeśli podtablica ma parzystą liczbę $n$n elementów i jeden podział ma $n/2$n, slash, 2, a drugi$$ n/2-1 elementów. W tych przypadkach każdy podział ma najwyżej $n/2$n, slash, 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: $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis.

Pokazanie, że czas wykonania typowego sortowania wynosi również $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis 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)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, patrząc na kilka innych przypadków. (Skoro mamy $O(n \log_2 n)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, wynika z tego oszacowanie $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, 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$3, n, slash, 4, a drugi $n/4$n, slash, 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$log, start base, 4, end base, n poziomach docieramy do podproblemu o rozmiarze 1. Dlaczego $\log_4 n$log, start base, 4, end base, 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$n. Innymi słowy, pytamy jaka wartość $x$x spełnia równanie $4^x=n$4, start superscript, x, end superscript, equals, n? Odpowiedzią jest $\log_4 n$log, start base, 4, end base, n. A co gdybyśmy wybrali ścieżkę prawych potomków? Ilustracja pokazuje, że zajmuje to $\log_{4/3} n$log, start base, 4, slash, 3, end base, n poziomów, aby dotrzeć do podproblemu rozmiaru 1. Dlaczego $\log_{4/3} n$log, start base, 4, slash, 3, end base, 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$n. Dla jakiej wartości $x$x spełnione jest równanie $(4/3)^x=n$left parenthesis, 4, slash, 3, right parenthesis, start superscript, x, end superscript, equals, n? Odpowiedzią jest $\log_{4/3} n$log, start base, 4, slash, 3, end base, n.

W każdym z pierwszych $\log_4 n$log, start base, 4, end base, n poziomów, znajduje się $n$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$c, n. 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$c, n. Razem, mamy $\log_{4/3} n$log, start base, 4, slash, 3, end base, n poziomów, więc całkowity czas podziału wynosi $O(n \log_{4/3})$O, left parenthesis, n, log, start base, 4, slash, 3, end base, right parenthesis. Istnieje zależność

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

tak więc $\log_{4/3} n$log, start base, 4, slash, 3, end base, n oraz $\log_2 n$log, start base, 2, end base, n różnią się jedynie czynnikiem $\log_2 (4/3)$log, start base, 2, end base, left parenthesis, 4, slash, 3, right parenthesis,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)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, 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$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)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, 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$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)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis

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)$O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis.

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.