Nから1人を雇う - ランクと確率

Question

CLRS Bookのアルゴリズムを勉強しています。私は間の違いを理解しようとします

• $ n $から$ i $ thを雇う確率
• ランクに基づいて$ n $の人から$ i $人を雇う確率。

通常の確率を使用すると、最初の答えの答えは$ frac {1} {ni} $であり、2番目の答えは$ frac {1} {i} $として与えられます。ここではコンセプトを理解できません。 $ frac {1} {i} $はどうですか？また、$ frac {1} {ni} $ランクを取得することもできますか？

n候補者がインターティックに並んでいます。

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 $候補のグループがランダムであるため、$ i $ -th候補は確率$ frac {1} {i}を持っているということです。彼/彼女が以前の$ I-1 $候補者よりも優れた資格がある場合に起こる選択された$。

今、到着に関するランダムな注文を検討する代わりに、 あなた自身の注文を課してください, 、ランクに基づく：最初の候補者は資格が低く、最後の候補は全体的に最高の候補です。この場合、グループが$ n $候補で構成されている場合、$ i $の候補者のために$ frac {1} {niである雇用の確率を$ i $ n-1 $に数えます。 } $、候補者は現在彼らのランクに基づいて到着しているため、$ i $ -th候補は以前の$ i-1 $よりも常に適格です。

これが、候補者のグループを誤って誘導したい理由です。そのため、特定の入力が候補者がランクごとにソートされる順列に関連する最悪の場合の動作を引き出すことができません。

CLRSは、このマイナーな変更により、最悪の場合は$ n $の代わりに、平均して$ o（ lg n）$候補者を雇うことができる方法を説明しています。これは確率的保証にすぎないことに注意してください。本当に不運であれば、ランクでソートされた候補者に対応する順列を生成することを擬似ランダムジェネレーターを防ぐものはありません。しかし、これが頻繁に発生するとは期待していません。悪い順列を生成する確率は、$ frac {1} {n！} $のみです。これは、大きな$ n $で非常に低いです。