Sélection aléatoire

L'algorithme de sélection aléatoire est le suivant:

Entrée: un tableau de nombres (distincts, pour simplifier) ​​et un nombren k ∈ [ n $A$$n$$k\in [n]$

Sortie: le " élément de rang " de A (c'est-à-dire celui en position k si A a été trié)A k $k$$A$$k$$A$

Méthode:

• S'il y a un élément dans $A$ , retournez-le
• Sélectionnez un élément $p$ (le "pivot") uniformément au hasard
• Calculez les ensembles $L = \{a\in A : a < p\}$ et $R = \{a\in A : a > p\}$
• Si $|L| \ge k$ , le retour du rang $k$ élément de $L$ .
• Sinon, retournez le rang $k - |L|$élément de $R$

On m'a posé la question suivante:

Supposons que $k=n/2$ , vous recherchez donc la médiane, et que $\alpha\in (1/2,1)$ soit une constante. Quelle est la probabilité que, lors du premier appel récursif, l'ensemble contenant la médiane ait une taille au plus $\alpha n$ ?

On m'a dit que la réponse est $2\alpha - 1$ , avec la justification "Le pivot sélectionné doit être compris entre $1−\alpha$ et $\alpha$ fois le tableau d'origine"

Pourquoi? Comme , tout élément choisi comme pivot est soit plus grand soit plus petit que plus de la moitié des éléments d'origine. La médiane se situe toujours dans le sous-tableau plus grand, car les éléments du sous-tableau partitionné sont toujours inférieurs au pivot.$\alpha \in (0.5, 1)$

Si le pivot se trouve dans la première moitié du tableau d'origine (moins de la moitié d'entre eux), la médiane sera sûrement dans la seconde moitié plus grande, car une fois la médiane trouvée, elle doit se trouver au milieu du tableau, et tout avant le pivot est plus petit comme indiqué ci-dessus.

Si le pivot se trouve dans la seconde moitié du tableau d'origine (plus de la moitié des éléments), la médiane sera sûrement la première moitié plus grande, pour la même raison, tout ce qui précède le pivot est considéré comme plus petit.

Exemple:

3 4 5 8 7 9 2 1 6 10

La médiane est de 5.

Supposons que le pivot choisi soit 2. Donc après la première itération, il devient:

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

Seulement 1et 2sont échangés après la première itération. Le numéro 5 (la médiane) est toujours dans la première moitié supérieure (selon le pivot 2). Le fait est que la médiane se situe toujours sur la moitié supérieure, comment peut-elle avoir une chance de rester dans un sous-réseau plus petit?

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