雇用一个人，排名和概率

Question

我正在研究CLRS书籍的算法。我试图理解

• 从$ n $中雇用$ i $ th人的概率和
• 根据排名，雇用$ n $人的$ i $ th人的概率。

使用正常概率，我们知道第一个的答案是$ frac {1} {ni} $，第二个答案的答案为CLRS书中的$ frac {1} {i} $。我在这里无法理解这个概念。 $ frac {1} {i} $如何？也可以是$ frac {1} {ni} $也是排名吗？

我们有N候选人排队参加Intertiew。一旦接受候选人，他将被授予等级。

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

当人们接受采访时 随机的 到达顺序，被雇用的候选$ i $的可能性为$ frac {1} {i} $。这是从以下事实来看的，假设每一个$ i $ $ i $ the $ i $ $ $ $ $ $ $ $ $ $ $ $ $ $ - 候选人具有概率$ frac {1} {i}的事实。被选中的$如果他/她比以前的$ I-1 $候选人更好的资格就会发生。

现在，而不是考虑到达的随机顺序，而是 强加自己的订单, ，基于等级：第一个候选人的资格较少，最后一个是最好的候选人。在这种情况下，如果该组由$ n $候选人制成，将它们从$ 0 $到$ n-1 $编号，那么您获得了$ i $ th候选人的概率，即$ frac {1} {ni } $，由于候选人现在是根据其排名来的，而$ i $ th的候选人总是比以前的$ i-1 $更好。

这就是为什么您要置入候选人组的原因：因此，没有特定的输入引起与候选人按等级排序的最坏情况。

CLR解释了这种较小的修改如何使您平均雇用$ O（ lg n）$候选人，而不是在最坏情况下雇用$ n $。请注意，这只是概率保证：如果您真的不幸，则没有任何阻止伪随机生成器，无法生成与等级分类的候选人相对应的置换。但是我们不希望这种情况经常发生：生成不良排列的概率仅为$ frac {1} {n！} $，对于大$ n $而言，它非常低。