Wybór losowy

14

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 ]Ank[n]

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

Metoda:

  • Jeśli w jest jeden element , zwróć goA
  • Wybierz element („pivot”) równomiernie losowop
  • Oblicz zestawy iL={aA:a<p}R={aA:a>p}
  • Jeśli , powrót rangi element .|L|kkL
  • W przeciwnym razie zwróć rangęelementk|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α(1/2,1)αn

Powiedziano mi, że odpowiedź to , z uzasadnieniem „Wybrany element przestawny powinien znajdować się między a razy pierwotna tablica”2α11αα

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.α(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?

Amumu
źródło
Nie zasiedliśmy w twoim wykładzie, więc proszę wyjaśnij metodę.
Raphael
Bez wiedzy na temat algorytmu, o którym mówisz, twoje pytanie nie jest czytelne. Wydaje się, że używasz na wiele sposobów; Próbowałem edytować, ale nie jestem pewien, czy zrozumiałem znaczenie. Popraw, aby pytanie było jasne. Głosowanie do zamknięcia do tego czasu. .5
Raphael
Jest to algorytm wyboru wykorzystujący metodę losową, w przeciwieństwie do metody deterministycznej.
Amumu,
Istnieje wiele sposobów losowego wyboru elementu.
Raphael
2
@Amumu: Zredagowałem go, aby opisać algorytm. Na takim forum nie wszyscy będą wiedzieć, o czym mówisz, i istnieje zupełnie inne randomizowane podejście do selekcji, które jest łatwiejsze do analizy.
Louis,

Odpowiedzi:

12

nαn(1α)n(1α)nα>1/222α12+2α=2α1

Louis
źródło
Dziękuję za odpowiedź. Nadal mam kilka rzeczy niejasnych. Co zatem ma wspólnego z α> 1/2 z zestawami rozłącznymi? Pomyślałem, że gdy zawsze mamy zestawy rozłączne przy użyciu tej metody, niezależnie od wielkości podtablicy.
Amumu
1α<1/2(1α)n<n(1α)n
Jeszcze jedna rzecz: co ma z tym wspólnego zły / dobry pivot? O ile mi wiadomo, dobry element przestawny jest na ogół w zakresie 25-75 (który dzieli oryginalne tablice na 25% -75%), a zły jest poza tym zakresem, a gorszy jest zwykle na początku lub na końcu oryginału szyk. Ale to?
Amumu,
2
αnα=3/4O()α