Randomized Selection

Question

L'algoritmo di selezione randomizzato è il seguente:

Input: Un array $ A $ di $ n $ (distinto, per semplicità) numeri e un numero $ k \ in [n] $

Output: Il il "rango $ k $ elemento" di $ A $ (vale a dire, quella in posizione di $ k $ se $ A $ è stato risolto)

Metodo:

• Se c'è un elemento in $ A $, restituirlo
• Selezionare un elemento $ p $ (il "pivot") in modo uniforme in modo casuale
• Calcolare il set di $ L = \ {a \ in A: un

  p \} $

• Se $ | L | \ Ge k $, restituire il rango $ k $ elemento di $ L $.
• In caso contrario, restituire il rango $ k - | L | $ elemento di $ R $

mi è stato chiesto alla seguente domanda:

Si supponga che $ k = n / 2 $, quindi si sta cercando per la mediana, e lasciare che $ \ alpha \ a (1 / 2,1) $ essere una costante. Qual è la probabilità che, alla prima chiamata ricorsiva, il set contenente la mediana ha formato al massimo $ \ alpha $ n?

mi è stato detto che la risposta è di $ 2 \ alpha - 1 $, con la giustificazione "Il perno selezionato deve essere compreso tra $ 1- \ alpha $ e $ \ alpha $ volte la matrice originale"

Perché? Come $ \ alpha \ a (0,5, 1) $, qualunque elemento viene scelto come perno è più grande o più piccola di più della metà gli elementi originali. La mediana sempre risiede nel sottoarray grande, perché gli elementi nel sottoarray partizionato sono sempre inferiori al perno.

Se la menzogna perno nella prima metà dell'array originale (meno della metà di essi), la mediana sarà sicuramente nel mezzo secondo più grande, perché una volta trovata la mediana, deve essere nella posizione centrale del matrice, e tutto prima il perno è inferiore come sopra indicato.

Se la menzogna perno nella seconda metà della matrice originale (più della metà degli elementi), la mediana sicuramente prima metà superiore, per la stessa ragione, tutto prima il perno è considerato più piccolo.

Esempio:

3 4 5 8 7 9 2 1 6 10

La mediana è 5.

Supposed il perno viene scelto 2. Così dopo la prima iterazione, diventa:

1 2 .... parte più grande ....

Solo 1 e 2 vengono scambiati dopo la prima iterazione. Numero 5 (la mediana) è ancora nella prima metà maggiore (accroding al perno 2). Il punto è, mediana sempre si trova su una maggiore della metà, come si può avere la possibilità di soggiorno in un sottoarray più piccolo?

Answer 1

Supponiamo che il vostro array ha $ n $ elementi. Come avrete notato, la mediana è sempre nella parte più grande dopo la prima partizione. La parte più grande ha dimensioni al massimo $ \ alpha $ n se la parte più piccola ha dimensioni di almeno $ (1- \ alpha) n $. Questo accade quando si sceglie un perno che non è una delle più piccole o più $ (1- \ alpha) n $ elementi. Poiché $ \ alpha> 1/2 $, si sa queste sono insiemi disgiunti, quindi la probabilità di colpire uno dei cattivi perni è di soli $ 2 - 2 \ alpha $ e $ 1- 2 + 2 \ alpha = 2 \ alpha - 1 $.