Wybór losowy

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 $A$$n$$k\in [n]$

Wyjście: Opcja „rangi Element” od (czyli jeden na pozycji jeśli została posortowana)$k$$A$$k$$A$

Metoda:

• Jeśli w jest jeden element , zwróć go$A$
• Wybierz element („pivot”) równomiernie losowo$p$
• Oblicz zestawy i$L = \{a\in A : a < p\}$$R = \{a\in A : a > p\}$
• Jeśli , powrót rangi element .$|L| \ge k$$k$$L$
• W przeciwnym razie zwróć rangęelement$k - |L|$$R$

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 ?$k=n/2$$\alpha\in (1/2,1)$$\alpha n$

Powiedziano mi, że odpowiedź to , z uzasadnieniem „Wybrany element przestawny powinien znajdować się między a razy pierwotna tablica”$2\alpha - 1$$1−\alpha$$\alpha$

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.$\alpha \in (0.5, 1)$

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 1i 2są 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?

$n$$\alpha n$$(1-\alpha) n$$(1-\alpha) n$$\alpha > 1/2$$2 - 2\alpha$$1- 2 + 2\alpha=2\alpha - 1$