2013-02-13 21 views
5

dwóch sposobów realizacji randomizowane Quicksort,randomizowane Quicksort

Metoda 1: Wybór losowy czop

Metoda 2: Generowanie losowej permutacji wejścia i wprowadzenie go do quicksort, że wybiera się pierwszy element w osi

Czy metoda1 jest taka sama jak metoda2 pod względem losowości?

Uwaga: Wygląda na to, że metoda 2 powoduje, że wszystkie partycje są równie prawdopodobne, ale metoda 1 nie. Więc jeśli nie są one takie same, to chcę zrozumieć, jaki jest wpływ na wydajność.

+0

Powiedziałbym, że tak. Partycja binarna na każdym kroku ma te same prawa w obu metodach. –

Odpowiedz

2

Tak. W obu przypadkach prawdopodobieństwo, że jakikolwiek konkretny element zostanie wybrany jako oś obrotu to 1/len (wejście). (Jednak druga metoda jest prawie na pewno wolniejsza dzięki stałemu współczynnikowi, ponieważ będzie wymagać dodatkowego linearnego przejścia do generowania losowej permutacji.)

+0

Ale dla konkretnego wejścia, druga metoda ma wszystkie n! Równie prawdopodobne są permutacje, ale pierwsza metoda nie zmienia względnej kolejności wprowadzania, więc nie obejmuje wszystkich możliwych partycji dla danych wejściowych. Czuję więc, że istnieje różnica, ale nie jestem pewna, jaki wpływ to będzie miało. –

+1

Nie jestem pewien, co masz na myśli przez "wszystkie możliwe partycje". Zestaw elementów, które są większe lub mniejsze niż element przestawny, nie zależy wcale od ich kolejności. – jacobm

+0

Przykro mi, że jestem zdezorientowany, rozumiem to teraz. Dzięki –