Sélection randomisée

Question

L'algorithme de sélection aléatoire est la suivante:

Entrée: Un tableau $ A $ Numéros de $ n $ (distinct, pour plus de simplicité) et un nombre k $ \ in [n] $

Sortie: La l "rang k $ $ element" de $ A $ (à savoir, l'une en position $ k $ a été réglé si $ A $)

Méthode:

• S'il y a un élément de $ A $, retourner
• Sélectionnez un élément $ p $ (le "pivot") uniformément au hasard
• Calculer les ensembles $ L = \ {a \ dans A:

  p \} $

• Si $ | L | \ Ge k $, retourner le rang $ élément k $ de $ L $.
• Dans le cas contraire, retourner k $ rang - | L | $ élément de $ R $

On m'a posé la question suivante:

  

Supposons que $ k = n / 2 $, de sorte que vous cherchez la médiane, et soit $ \ alpha \ in (1 / 2,1) $   être une constante. Quelle est la probabilité que, lors du premier appel récursif, la   ensemble contenant la médiane a une taille au plus $ \ alpha $ n?

On m'a dit que la réponse est de 2 $ \ alpha - 1 $, avec la justification "Le pivot choisi doit se situer entre $ 1 \ alpha $ et $ \ alpha fois de $ le tableau original"

Pourquoi? Comme $ \ alpha \ in (0,5, 1) $, quel que soit l'élément est choisi comme pivot est soit plus grande ou plus petite que plus de la moitié des éléments d'origine. La médiane toujours réside dans le sous-tableau plus grand, parce que les éléments du sous-tableau partitionné sont toujours moins que le pivot.

Si les mensonges de pivot dans la première moitié du tableau d'origine (moins de la moitié d'entre eux), la médiane sera certainement dans la deuxième plus grande moitié, car une fois la médiane se trouve, il doit être dans la position médiane du tableau, et tout avant que le pivot est inférieur comme indiqué ci-dessus.

Si les mensonges de pivot dans la seconde moitié du tableau d'origine (plus de la moitié des éléments), la médiane sera sûrement plus de la moitié d'abord, pour la même raison, tout avant que le pivot est considéré comme plus petit.

Exemple:

3 4 5 7 8 9 2 1 6 10

La médiane est 5.

Censé le pivot choisi est 2. Ainsi, après la première itération, il devient:

1 2 .... plus partie ....

Seuls 1 et 2 sont permutés après la première itération. Number 5 (la médiane) est toujours dans la première moitié de la plus grande (accroding au pivot 2). Le point est, toujours médiane se trouve sur plus de la moitié, comment peut-il avoir une chance de rester dans un plus petit sous-tableau?

Answer 1

Supposons que votre tableau a $ n éléments $. Comme vous l'avez noté, la médiane est toujours dans la plus grande partie après la première partition. La partie plus grande taille a au plus $ \ alpha n $ si la plus petite partie a une taille au moins $ (1 \ alpha) n $. Cela se produit lorsque vous choisissez un pivot qui est pas l'un des plus petit ou plus grand $ (1- \ alpha) n éléments $. Parce que $ \ alpha> 1/2 $, vous savez ce sont des ensembles disjoints, donc la probabilité d'atteindre l'un des mauvais pivots est à seulement 2 $ - 2 \ alpha $ et 1 $ 2 + 2 \ alpha = 2 \ alpha - 1 $.