Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania

Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być $O(n^2)$ , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych tekstach [1] [2] jego najgorszy przypadek złożoności zapisano jako $O(n\log{n})$

Co jest poprawne

Oba źródła odnoszą się do „najgorszego oczekiwanego czasu działania” Zgaduję, że odnosi się to do oczekiwanego czasu, który różni się od absolutnie najgorszego przypadku.$O(n \log n).$

Quicksort zwykle wymaga bezwzględnego najgorszego przypadku . Najgorszy przypadek występuje, gdy na każdym etapie procedura podziału dzielitablicę o długości n na tablice o rozmiarze 1 i n - 1 . Ten „pechowy” wybór elementów przestawnych wymaga O ( n ) wywołań rekurencyjnych, co prowadzi donajgorszego przypadku O ( n 2 ) .$O(n^2)$$n$$1$$n-1$$O(n)$$O(n^2)$

Losowe lub losowe tasowanie tablicy przestawnej przed sortowaniem powoduje, że najgorszy przypadek jest bardzo mało prawdopodobny, szczególnie w przypadku dużych tablic. Zobacz Wikipedię, aby uzyskać dowód, że oczekiwany czas to $O(n\log n)$ . Według innego źródła „prawdopodobieństwo, że quicksort użyje kwadratowej liczby porównań podczas sortowania dużej tablicy na twoim komputerze, jest znacznie mniejsze niż prawdopodobieństwo, że twój komputer zostanie uderzony piorunem”.

Edytować:

Zgodnie z komentarzem Bangye'a można wyeliminować sekwencję wyboru obrotu w najgorszym przypadku, zawsze wybierając element środkowy jako oś obrotu. Ponieważ znalezienie mediany zajmuje czas , daje to Θ ( n log n ) wydajność najgorszego przypadku. Ponieważ jednak losowe szybkie sortowanie jest bardzo mało prawdopodobne, aby natknąć się na najgorszy przypadek, rzadko stosuje się deterministyczny wariant szybkiego wyszukiwania.$O(n)$$\Theta(n \log n)$

Brakowało Ci, że te teksty mówią o „najgorszym oczekiwanym przypadku czasie działania”, a nie „najgorszym przypadku”.

Omawiają implementację Quicksort, która obejmuje element losowy. Zwykle masz algorytm deterministyczny, czyli algorytm, który dla danego wejścia zawsze będzie generował dokładnie te same kroki. Aby określić „najgorszy czas działania”, należy przeanalizować wszystkie możliwe dane wejściowe i wybrać ten, który generuje najgorszy czas działania.

Ale tutaj mamy czynnik losowy. Biorąc pod uwagę pewne dane wejściowe, algorytm nie zawsze wykona te same kroki, ponieważ w grę wchodzi pewna losowość. Zamiast mieć środowisko wykonawcze dla każdego ustalonego wejścia, mamy „oczekiwany czas działania” - sprawdzamy każdą możliwą wartość losowych decyzji i ich prawdopodobieństwo, a „oczekiwany czas działania” jest średnią ważoną czasu działania dla każdej kombinacji decyzji losowych , ale wciąż dla stałego wejścia.

Dlatego obliczamy „oczekiwany czas działania” dla każdego możliwego wejścia, a aby uzyskać „najgorszy oczekiwany czas działania”, znajdujemy jedno możliwe wejście, w którym oczekiwany czas działania jest najgorszy. I najwyraźniej pokazali, że najgorszym przypadkiem „oczekiwanego czasu działania” jest po prostu O (n log n). Nie zdziwiłbym się, gdyby tylko losowe wybranie pierwszego punktu przestawienia zmieniłoby najgorszy oczekiwany czas działania na o (n ^ 2) (małe o zamiast dużego O), ponieważ tylko kilka z n osi przestawi się na najgorszy przypadek zachowanie.

Zauważ, że są dwa wziąć pod uwagę rzeczy ponad średnią: permutację wejściową i osie przestawne (jedna na partycjonowanie).

W przypadku niektórych danych wejściowych i implementacji Quicksort wszystkie pivoty są złe ( razy ta sama liczba czasami działa), więc randomizacja nie pomaga. W takim przypadku oczekiwany czas (uśrednianie w stosunku do wyborów obrotowych) może być kwadratowy w najgorszym przypadku (złe wejście). Nadal „ogólny” oczekiwany czas (uśrednianie dla obu danych wejściowych i opcji obrotu) nadal wynosi Θ $n$$\Theta(n \log n)$

Inne implementacje mają rzeczywisty najgorszy czas działania w $\Theta(n \log n)$ , a mianowicie te, które wybierają dokładną medianę jako oś przestawną i ładnie radzą sobie z duplikatami.

Podsumowując, sprawdź źródła (źródła), których implementacji używają i jaką ilość uważają za losową lub. naprawione w ich analizie.

$O(n^2)$

Najgorszym przypadkiem dla randomizowanego szybkiego sortowania są te same elementy, co dane wejściowe. Np .: 2,2,2,2,2,2

$T(n) = T(n-1) + n$$O(n^2)$