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

18

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(n2) , 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(nlogn)

Co jest poprawne

Atinesz
źródło
3
Powinieneś ten „jakiś tekst”, o którym mówisz. Coś tam jest ukryte. Znajdziesz go, jeśli ponownie przeczytasz ten „tekst”
AJed
Uwaga: Link [1] nie działa. Link [2] wyraźnie stwierdza, że ​​algorytm jest losowy, więc dla każdego wejścia nie masz „środowiska uruchomieniowego”, ale „oczekiwany czas działania”. Oczekiwany czas działania dla najgorszego możliwego wejścia to O (n log n).
gnasher729

Odpowiedzi:

18

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(nlogn).

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(n2))n1n-1O(n)O(n2))

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(nlogn) . 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)Θ(nlogn)

James Evans
źródło
Ogólnie rzecz biorąc, możemy powiedzieć, że w najgorszym przypadku zachowuje się on jako kwadratowy
Atinesh
@Atinesh Nie, przynajmniej jeśli masz na myśli . Θ
Raphael
Myślę, że słuszne jest stwierdzenie, że najgorszym przypadkiem wykonania randomizowanego szybkiego sortowania jest O(n2)).
James Evans
4
Θ(nlogn)
6

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.

gnasher729
źródło
2

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Θ(nlogn)

Inne implementacje mają rzeczywisty najgorszy czas działania w Θ(nlogn) , 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.

Raphael
źródło
Zastanów się nad pytaniem postimg.org/image/fiurc4z87, które zadałem na egzaminie. Jakie właściwe odpowiedzi sugerujesz, myślę (c)
Atinesh
1
@Atinesh Myślę, że moja odpowiedź zawiera wystarczającą ilość informacji na ten temat.
Raphael
-1

O(n2))

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)+nO(n2))

pratyay
źródło
Tak jest, jeśli masz wyjątkowo głupią implementację Quicksort. Każda przyzwoita implementacja będzie w pierwszej partycji wymieniać nr 1 i nr 6, nr 2 i nr 5, nr 3 i nr 4, a następnie posortować dwie podgrupy o długości 3.
gnasher729,
Wydaje mi się, że masz <= oraz> = na obu wskaźnikach skanujących z LHS i RHS. Dlatego tak mówisz. „=” jest powiązane z jednym ze wskaźników, a nie z obydwoma. W takim przypadku drzewo rekurencji rośnie do n.
pratyay
I to nazywam niezwykle głupią implementacją. Każda implementacja, która zajmuje kwadratowe środowisko wykonawcze dla przypadku „wszystkie elementy są równe”, jest kryminalnie głupia. W rzeczywistości istnieją implementacje, które zajmują w tym przypadku czas liniowy (O (n), a nie O (n log n)).
gnasher729