知识卡片
在线雇用先观察再选择
在线雇用只能当场接受或拒绝。
总共有 n 名候选人时,先拒绝前 k 人并记下其中最高分,再录用之后第一个超过该门槛的人。均匀随机顺序下,若全体最优者出现在位置 i>k,算法成功还要求前 i−1 人中的最佳者落在观察期;这两件事的概率乘积为 (1/n)·(k/(i−1))=k/[n(i−1)]。
对所有 i=k+1…n 的互斥位置求和,并取 k≈n/e,可保证成功概率至少约 1/e。这个结论依赖候选顺序是均匀随机排列。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第5章 概率分析和随机算法 · 查看原书依据
Thus, if you implement our strategy with k = n/e, you succeed in hiring the best-qualified applicant with probability at least 1/e.
参考来源
- 位置:《算法导论(第4版)》第 5 章 5.4 节与 Problems(`OEBPS/chapter005.xhtml`,文本字符 [45000, 50000);公式图 Art_P291–P297)。
- 结论依据:5.4.4 节策略先拒绝 k 人,再接受首个超过观察期最佳的人;在均匀随机排列下对最优者位置求和,k≈n/e 给出至少 1/e 的成功率。
- 原始内容:Thus, if you implement our strategy with k = n / e , you succeed in hiring the best-qualified applicant with probability at least 1/ e .