L'embauche d'une personne sur n - rang et probabilité

Question

Je suis en train d'étudier les algorithmes de livre CLRS. J'essaie de comprendre la différence entre

• probabilité d'embauche $ i $ e personne de $ n $ et
• probabilité d'embauche i $ $ e personne de personnes $ n $ basé sur les rangs.

En utilisant la probabilité normale, nous connaissons la réponse pour le premier est $ \ frac {1} {ni} $ et la réponse à la seconde est donnée comme $ \ frac {1} {i} $ dans le livre de CLRS . Je suis incapable de comprendre le concept ici. Comment est-il $ \ frac {1} {i} $? Peut-il être aussi $ \ frac {1} {n-i} $ prise en rangs aussi?

Nous avons n candidats alignés pour un intertiew.Once un candidat est interviewé, il reçoit un rank.If le rang du prochain candidat est plus le plus grand grade actuel, il est engagé et son rang est maintenant le plus grand rang actuel

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i

Answer 1

Quand les gens sont interviewés après une au hasard ordre d'arrivée, la probabilité de candidat $ i $ est d'être embauché $ \ frac {1} {i} $. Cela découle du fait que, en supposant un ordre aléatoire des arrivées, pour chaque $ i $ le groupe de départ $ i $ candidats est aléatoire, de sorte que le i $ $ candidat -ème a une probabilité $ \ frac {1} {i} $ d'être choisi qui arrive s'il / elle est mieux qualifié que le précédent $ i-1 candidats $.

Maintenant, au lieu de considérer un ordre aléatoire sur les arrivées, imposer votre propre commande , basé sur les rangs: le premier candidat est le moins qualifié, et le dernier est celui qui est le meilleur dans l'ensemble . Dans ce cas, si le groupe est de $ n candidats $, les numérotant de 0 $ à $ n-1 $ vous obtenez pour i $ $ e candidat une probabilité d'être embauché qui est $ \ frac {1} {ni } $, étant donné que les candidats arrivent maintenant sur la base de leurs rangs, et $ i $ candidat -ème est toujours mieux qualifié que le précédent $ i-1 $.

Ceci est la raison pour laquelle vous voulez permute le groupe de candidats. De sorte qu'aucune entrée particulière provoque le pire comportement de cas associé à la permutation dans laquelle les candidats sont classés par rang

CLRS explique comment ces modifications mineures vous permet de louer, en moyenne, $ O (\ logn) $ candidats au lieu de $ n $ dans le pire des cas. Notez que ceci est seulement une garantie probabiliste: rien empêche le générateur pseudo-aléatoire, si vous êtes vraiment malchanceux, de générer la permutation correspondant aux candidats classés par rang. Mais nous ne pensons pas que cela se produise souvent: la probabilité de générer la mauvaise permutation est seulement $ \ frac {1} {! N} $ qui, pour une grande $ n $, est très faible

.