Ostre stężenie do wyboru przez losowe dzielenie?

Zwykły prosty algorytm znajdowania elementu mediany w tablicy liczby to: $A$ $n$

Próbkuj elementów z z zamianą na $n^{3/4}$ $A$ $B$
Sortuj i znaleźć rangi elementy i z $B$ $|B|\pm \sqrt{n}$ $l$ $r$ $B$
Sprawdź, czy i znajdują się po przeciwnych stronach mediany i czy istnieje co najwyżej elementów w między i dla pewnej odpowiedniej stałej . Niepowodzenie, jeśli tak się nie stanie. $l$ $r$ $A$ $C\sqrt{n}$ $A$ $l$ $r$ $C > 0$
W przeciwnym razie, znaleźć mediany sortowania elementów między i $A$ $l$ $r$

Nietrudno zauważyć, że przebiega to w czasie liniowym i że z dużym prawdopodobieństwem się udaje. (Wszystkie złe zdarzenia są dużymi odchyleniami od oczekiwań na dwumian.)

Alternatywnym algorytmem dla tego samego problemu, który jest bardziej naturalny dla uczniów, którzy widzieli szybkie sortowanie, jest opisany tutaj: Wybór losowy

Łatwo też zauważyć, że ten ma liniowy oczekiwany czas działania: powiedzmy, że „runda” jest sekwencją wywołań rekurencyjnych, które kończą się, gdy daje się podział 1 / 4-3 / 4, a następnie obserwujemy, że oczekiwana długość runda wynosi co najwyżej 2. (W pierwszym losowaniu rundy prawdopodobieństwo uzyskania dobrego podziału wynosi 1/2, a następnie po rzeczywistym wzroście, tak jak opisano algorytm, więc długość rundy jest zdominowana przez losową zmienną geometryczną).

Więc teraz pytanie:

Czy można wykazać, że losowa selekcja przebiega w czasie liniowym z dużym prawdopodobieństwem?

Mamy rundy , a każda runda ma długość co najmniej z prawdopodobieństwem co najwyżej , więc granica związku oznacza, że czas działania wynosi z prawdopodobieństwem $O(\log n)$ $k$ $2^{-k+1}$ $O(n\log\log n)$ $1-1/O(\log n)$ .

To trochę niezadowalające, ale czy to w rzeczywistości prawda?

algorithms algorithm-analysis randomized-algorithms Louis
źródło

Wyjaśnij, do którego algorytmu odnoszą się twoje pytania.

Raphael

Czy pytasz, czy prawidłowo zastosowałeś związek związkowy, czy też istnieje lepszy, bardziej satysfakcjonujący związek?

Joe

@Joe Ten drugi. Chodzi o to, że rundy są artefaktem, dzięki któremu długość rundy jest zdominowana przez geometrię. Następnie anaylisys „zapomina”, czy algorytm wyprzedza, czy opóźnia ten, który zawsze ma podział 1 / 4-3 / 4 na nosie, aby uniezależnić geometrię. Pytam, czy to „oszukiwanie”, jak ujął to Yuval, jest nadal ścisłe.

Louis,

Odpowiedzi:

To nieprawda, że algorytm działa z dużym prawdopodobieństwem w czasie liniowym. Biorąc pod uwagę tylko pierwszą rundę, czas działania wynosi co najmniej razy zmienna losowa . Niech będzie dopuszczalnym prawdopodobieństwem awarii. Ponieważ , czas działania wynosi co najmniej . $\Theta(n)$ $G(1/2)$ $p(n) \longrightarrow 0$ $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$ $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

(W grę wchodzi oszustwo, ponieważ długość pierwszej rundy nie jest tak naprawdę . Bardziej szczegółowa analiza może lub nie może potwierdzić tę odpowiedź.) $G(1/2)$

Edycja: Grübel i Rosler udowodnili, że oczekiwana liczba porównań podzielona przez zmierza (w pewnym sensie) do pewnego rozkładu granic, który jest nieograniczony. Zobacz na przykład artykuł Grübla „Algorytm wyboru Hoare'a: podejście łańcuchowe Markowa”, który odwołuje się do ich oryginalnej pracy. $n$

Yuval Filmus
źródło

Niepokoi mnie to. Jak powiedziałem w moim komentarzu powyżej, rundy są po prostu sposobem na analizę „spowolnionej” wersji algorytmu, która czeka, aż osiągnie wystarczająco dobrą wartość obrotu, aby kontynuować. Pokazujesz, że dla każdego ustalonego prawdopodobieństwo, że pierwsza runda wymaga więcej niż osi obrotu, wynosi . Zasadniczo jednak długą pierwszą rundę można zrównoważyć pustą drugą rundą, w tym sensie, że na końcu algorytm „nie spowolnionego” dogonił ten, który zawsze dzieli 1 / 4-3 / 4 .

C > 0

$C>0$

C

$C$

> 0

$>0$

Louis,

To nie jest prawda, jeśli pierwsza runda jest długa, to cały czas trwania jest długi, ponieważ kolejne rundy nie mogą skrócić czasu trwania. Chodzi o to, że dla dowolnego pierwsza runda wymaga czasu co najmniej z pewnym stałym prawdopodobieństwem .

C

$C$

C n

$Cn$

p_{C} > 0

$p_C > 0$

Yuval Filmus,

Jestem teraz szczęśliwszy, ponieważ okrągła długość jest niewiele mniejsza niż geometryczna zastosowana do górnej granicy. Wydaje mi się, że to właśnie G&R wywołują gwałtowność. Niezła odpowiedź.

Louis,