If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

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, 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, minus, 1 elementów.
Tak jak w sortowaniu przez scalanie, czas na określone wywołanie rekursywne na n-elementowej podtablicy wynosi \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ł.

Czas wykonania w najgorszym przypadku

W sortowaniu szybkim najbardziej niezrównoważone podziały są zawsze możliwe. W takim przypadku oryginalne wywołanie zajmuje c, n porównań, dla pewnej stałej c, wywołanie rekursywne na n, minus, 1 elementów wymaga c, left parenthesis, n, minus, 1, right parenthesis porównań, wywołanie rekursywne na n, minus, 2 elementów wymaga 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:
Rysunek ilustrujący najgorszy przypadek w dla algorytmu szybkiego sortowania z diagramem drzewkowym po lewej stronie i czasami podziału po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total partitioning time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas podziału wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, 0 i n minus 1, a czas podziału wynosi c razy n minus 1. Na trzecim poziomie znajdują się dwa węzły, 0 i n minus 2, a czas podziału wynosi c razy n minus 2. Na czwartym poziomie znajdują się dwa węzły, 0 i n minus 3, a czas podziału wynosi c razy n minus 3. Wielokropek poniżej sugeruje, że drzewko rozwija się dalej w ten sam sposób. Na przedostatnim poziomie drzewo ma jeden węzeł, z czasem podziału 2 razy c, a na ostatnim poziomie mamy dwa węzły, 0 i 1, z czasem podziału równym 0.
Gdy podsumujemy ilość podziałów dla każdego poziomu, otrzymamy
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) . \begin{aligned} cn + c(n-1) + c(n-2) + \cdots + 2c &= c(n + (n-1) + (n-2) + \cdots + 2) \\ &= c((n+1)(n/2) - 1) \ . \end{aligned}
Ostatnie wyrażenie wynika z faktu, że 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, left parenthesis, n, squared, right parenthesis

Czas wykonania w najlepszym przypadku

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 left parenthesis, n, minus, 1, right parenthesis, slash, 2 elementów. Drugi przypadek występuje, jeśli podtablica ma parzystą liczbę n elementów i jeden podział ma n, slash, 2, a drugi n/2-1 elementów. W tych przypadkach każdy podział ma najwyżej 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:
Rysunek ilustrujący najlepszy przypadek w dla algorytmu szybkiego sortowania z diagramem drzewkowym po lewej stronie i czasami podziału po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total partitioning time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas podziału wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, każdy z nich mniejszy lub równy 1/2 n, a czas podziału jest mniejszy lub równy 2 razy c razy 1/2 n, czyli tyle samo, co c razy n. Na trzecim poziomie znajdują się cztery węzły, każdy z nich mniejszy lub równy 1/4 n, a czas podziału jest mniejszy lub równy 4 razy c razy 1/4 n, czyli tyle samo, co c razy n. Na czwartym poziomie znajduje się osiem węzłów, każdy z nich mniejszy lub równy 1/8 n, a czas podziału jest mniejszy lub równy 8 razy c razy 1/8 n, czyli tyle samo, co c razy n. Wielokropek poniżej sugeruje, że drzewko rozwija się dalej w ten sam sposób. Na najniższym poziomie znajduje się n węzłów po 1, a czas podziału jest mniejszy lub równy n razy c, tyle samo, co c razy n.
Jeśli zastosujemy notację duże-Θ, otrzymamy wynik identyczny jak w przypadku sortowania przez scalanie: \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis.

Średni czas wykonania

Pokazanie, że czas wykonania typowego sortowania wynosi również \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, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, patrząc na kilka innych przypadków. (Skoro mamy O, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, wynika z tego oszacowanie \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 3, n, slash, 4, a drugi 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:
Diagram dla typowej, średniej sytuacji w przypadku szybkiego sortowania
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, start base, 4, end base, n poziomach docieramy do podproblemu o rozmiarze 1. Dlaczego 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. Innymi słowy, pytamy jaka wartość x spełnia równanie 4, start superscript, x, end superscript, equals, n? Odpowiedzią jest log, start base, 4, end base, n. A co gdybyśmy wybrali ścieżkę prawych potomków? Ilustracja pokazuje, że zajmuje to log, start base, 4, slash, 3, end base, n poziomów, aby dotrzeć do podproblemu rozmiaru 1. Dlaczego 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. Dla jakiej wartości x spełnione jest równanie left parenthesis, 4, slash, 3, right parenthesis, start superscript, x, end superscript, equals, n? Odpowiedzią jest log, start base, 4, slash, 3, end base, n.
W każdym z pierwszych log, start base, 4, end base, 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 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 c, n. Razem, mamy log, start base, 4, slash, 3, end base, n poziomów, więc całkowity czas podziału wynosi O, left parenthesis, n, log, start base, 4, slash, 3, end base, right parenthesis. Istnieje zależność
log, start base, a, end base, n, equals, start fraction, log, start base, b, end base, n, divided by, log, start base, b, end base, a, end fraction
dla wszystkich liczb dodatnich a, b, i n. Podstawiając a, equals, 4, slash, 3 i b, equals, 2, otrzymujemy
log, start base, 4, slash, 3, end base, n, equals, start fraction, log, start base, 2, end base, n, divided by, log, start base, 2, end base, left parenthesis, 4, slash, 3, right parenthesis, end fraction, space, comma
tak więc log, start base, 4, slash, 3, end base, n oraz log, start base, 2, end base, n różnią się jedynie czynnikiem 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, 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-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, 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-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, 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, left parenthesis, n, log, start base, 2, end base, n, right parenthesis.

Sortowanie szybkie z randomizacją

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.