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 n1 elementów - wszystkie, oprócz elementu rozdzielającego. Na skutek tego wywołania rekursywne będą działać na podtablicach o rozmiarach 0 i n1 elementów.
Tak jak w sortowaniu przez scalanie, czas na określone wywołanie rekursywne na n-elementowej podtablicy wynosi Θ(n). 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 cn porównań, dla pewnej stałej c, wywołanie rekursywne na n1 elementów wymaga c(n1) porównań, wywołanie rekursywne na n2 elementów wymaga c(n2) 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
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) .
Ostatnie wyrażenie wynika z faktu, że 1+2+3++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 Θ(n2)

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 (n1)/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: Θ(nlog2n).

Średni czas wykonania

Pokazanie, że czas wykonania typowego sortowania wynosi również Θ(nlog2n) wymaga dość zaawansowanej matematyki, zatem nie będziemy się w to zagłębiać. Natomiast możemy spróbować zrozumieć, dlaczego jest to O(nlog2n), patrząc na kilka innych przypadków. (Skoro mamy O(nlog2n), wynika z tego oszacowanie Θ(nlog2n), 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 log4n poziomach docieramy do podproblemu o rozmiarze 1. Dlaczego log4n 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 4x=n? Odpowiedzią jest log4n. A co gdybyśmy wybrali ścieżkę prawych potomków? Ilustracja pokazuje, że zajmuje to log4/3n poziomów, aby dotrzeć do podproblemu rozmiaru 1. Dlaczego log4/3n 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 log4/3n.
W każdym z pierwszych log4n 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 log4/3n poziomów, więc całkowity czas podziału wynosi O(nlog4/3). Istnieje zależność
logan=logbnlogba
dla wszystkich liczb dodatnich a, b, i n. Podstawiając a=4/3 i b=2, otrzymujemy
log4/3n=log2nlog2(4/3) ,
tak więc log4/3n oraz log2n różnią się jedynie czynnikiem log2(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(nlog2n), 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(nlog2n), 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(nlog2n)
Miej na uwadze, że ta analiza _nie_jestmatematycznie ścisła, ale daje intuicyjny wgląd, że czas wykonywania średniego przypadku może być O(nlog2n).

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.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.