concentrazione Sharp per la selezione tramite il partizionamento casuale?

Question

L'algoritmo semplice usuale per trovare l'elemento mediano in un array $ A $ di $ n $ numeri è:

• $ Esempio n ^ {3/4} $ elementi da $ A $ con sostituzione in $ B $
• Ordina $ B $ e trovare il rango $ | B | \ pm \ sqrt {n} $ elementi $ l $ e $ R $ di $ B $
• Verificare che $ l $ e $ R $ sono su lati opposti del mediano di $ A $ e che ci sono al massimo $ C \ sqrt {n} $ elementi in $ A $ tra $ l $ e $ R $ per qualche costante appropriata $ C> 0 $. Fail se questo non accade.
• In caso contrario, trovare la mediana di classificare gli elementi di $ A $ tra $ l $ e $ R $

Non è difficile vedere che questo viene eseguito in tempo lineare e che ci riesce con alta probabilità. (Tutti gli eventi negativi sono grandi deviazioni dalla previsione di un binomio.)

Un algoritmo alternativo per lo stesso problema, che è più naturale per insegnare agli studenti che hanno visto rapido tipo è quello descritto qui: Randomized Selezione

È anche facile vedere che questo ha lineare durata previsto: dire che un "giro" è una sequenza di chiamate ricorsive che termina quando si dà una / 4-3 / 4 divisione 1, e quindi osservare che la durata prevista di un round è al massimo 2. (Nel primo sorteggio di un round, la probabilità di ottenere una buona divisione è 1/2 e poi dopo in realtà aumenta, come l'algoritmo è stato descritto in modo lunghezza rotonda è dominato da una geometrica casuale variabile.)

Così ora la domanda:

E 'possibile dimostrare che corre di selezione randomizzati in tempo lineare con alta probabilità?

Abbiamo $ O (\ log n) $ turni, e ogni turno ha una lunghezza di almeno $ k $ con probabilità al massimo $ di 2 ^ {- k + 1} $, quindi un'unione legata dà che il tempo di esecuzione è di $ O (n \ log \ log n) $ con probabilità $ 1-1 / O (\ log n) $.

Questa è una specie di insoddisfacente, ma è in realtà la verità?

Answer 1

Non è vero che l'algoritmo viene eseguito in tempo lineare con alta probabilità. Considerando solo il primo giro, il tempo di esecuzione è almeno $ \ theta (n) $ volte $ G (1/2) $ variabile casuale. Sia $ p (n) \ longrightarrow 0 $ essere la probabilità di guasto consentito. Dal momento che $ \ Pr [G (1/2) \ geq \ log_2 p (n) ^ {- 1}] = p (n) $, il tempo di esecuzione è di almeno $ \ Omega (n \ log_2 p (n) ^ {-1}) = \ omega (n) $.

(V'è una certa truffa coinvolti, dal momento che la lunghezza del primo round non è in realtà $ G (1/2) $. Un'analisi più attenta potrebbe o non potrebbe convalidare questa risposta.)

Modifica: Grübel e Rosler hanno dimostrato che il numero atteso di confronti diviso per $ n $ tende (in un certo senso) in una certa distribuzione limite, che è illimitata. Vedere per la carta l'esempio di Grübel "algoritmo di selezione di Hoare: un approccio catena di Markov"., Che fa riferimento il documento originale