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ść.
Powiedziałbym, że tak. Partycja binarna na każdym kroku ma te same prawa w obu metodach. –