Algorytm losowego wyboru jest następujący:
Dane wejściowe: tablica składająca się z n (odrębnych, dla uproszczenia) liczb i liczby k ∈ [ n ]
Wyjście: Opcja „rangi Element” od (czyli jeden na pozycji jeśli została posortowana)
Metoda:
- Jeśli w jest jeden element , zwróć go
- Wybierz element („pivot”) równomiernie losowo
- Oblicz zestawy i
- Jeśli , powrót rangi element .
- W przeciwnym razie zwróć rangęelement
Zadano mi następujące pytanie:
Załóżmy, że , więc szukasz mediany i niech będzie stałą. Jakie jest prawdopodobieństwo, że przy pierwszym wywołaniu rekurencyjnym zestaw zawierający medianę ma rozmiar co najwyżej ?
Powiedziano mi, że odpowiedź to , z uzasadnieniem „Wybrany element przestawny powinien znajdować się między a razy pierwotna tablica”
Dlaczego? Jako , każdy element wybrany jako oś obrotu jest większy lub mniejszy niż więcej niż połowa oryginalnych elementów. Mediana zawsze leży w większej podtablicy, ponieważ elementy podzielonej na podgrupy elementów są zawsze mniejsze niż oś obrotu.
Jeśli oś obrotu znajduje się w pierwszej połowie oryginalnej tablicy (mniej niż połowa z nich), mediana z pewnością znajdzie się w drugiej większej połowie, ponieważ po znalezieniu mediany musi znajdować się w środkowej pozycji tablicy, a wszystko przed osią obrotu jest mniejsze, jak stwierdzono powyżej.
Jeśli oś obrotu znajduje się w drugiej połowie oryginalnej tablicy (więcej niż połowa elementów), mediana z pewnością pierwsza większa połowa, z tego samego powodu, wszystko przed osią obrotu jest uważane za mniejsze.
Przykład:
3 4 5 8 7 9 2 1 6 10
Mediana wynosi 5.
Załóżmy, że wybrany element przestawny ma wartość 2. Zatem po pierwszej iteracji staje się:
1 2 .... większa część ....
Tylko 1
i 2
są zamieniane po pierwszej iteracji. Liczba 5 (mediana) wciąż znajduje się w pierwszej większej połowie (zgodnie z osią 2). Chodzi o to, że mediana zawsze leży na większej połowie, jak może mieć szansę na pozostanie w mniejszej podtablicy?
Odpowiedzi:
źródło