Sélection aléatoire

14

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

Entrée: un tableau de nombres (distincts, pour simplifier) ​​et un nombren k [ n ]Ank[n]

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

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={aA:a<p} et R={aA:a>p}
  • Si |L|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 α(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 αn ?

On m'a dit que la réponse est 2α-1 , avec la justification "Le pivot sélectionné doit être compris entre 1-α et α 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.α(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?

Amumu
la source
Nous n'avons pas participé à votre conférence, veuillez donc expliquer la méthode.
Raphael
Sans savoir de quel algorithme précis vous parlez, votre question n'est pas lisible. Vous semblez utiliser à plusieurs titres; J'ai essayé d'éditer mais je ne suis pas sûr d'avoir saisi le sens. Veuillez réviser afin que la question soit claire. Voter pour clôturer jusque-là. .5
Raphael
C'est l'algorithme de sélection utilisant la méthode aléatoire, par opposition à la méthode déterministe.
Amumu
Il existe de nombreuses façons de sélectionner un élément au hasard.
Raphael
2
@Amumu: Je l'ai édité pour décrire l'algorithme. Dans un forum comme celui-ci, tout le monde ne saura pas de quoi vous parlez, et il existe une approche aléatoire très différente de la sélection qui est plus facile à analyser.
Louis

Réponses:

12

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 / 2nαn(1-α)n(1-α)nα>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α .1-2+2α=2α-1

Louis
la source
Merci d'avoir répondu. J'ai encore quelques choses peu claires. Alors, qu'est-ce que α> 1/2 a quelque chose à voir avec les ensembles disjoints? J'ai pensé que lorsque nous avons toujours des ensembles disjoints avec cette méthode, quelle que soit la taille du sous-tableau.
Amumu
1α<1/2(1-α)n<n-(1-α)n
Une dernière chose: qu'est-ce que le mauvais / bon pivot a à voir avec ça? Pour autant que je sache, un bon pivot est généralement dans une plage de 25 à 75 (ce qui divise les tableaux d'origine de 25 à 75%), et le mauvais est en dehors de cette plage, et le pire est généralement au début ou à la fin de l'original tableau. Mais ça?
Amumu
2
αnα=3/4O()α