知识卡片

普通读书笔记卡 · 3605.a

在线雇用先观察再选择

理解等级:中级

在线雇用只能当场接受或拒绝。

总共有 n 名候选人时,先拒绝前 k 人并记下其中最高分,再录用之后第一个超过该门槛的人。均匀随机顺序下,若全体最优者出现在位置 i>k,算法成功还要求前 i−1 人中的最佳者落在观察期;这两件事的概率乘积为 (1/n)·(k/(i−1))=k/[n(i−1)]。

对所有 i=k+1…n 的互斥位置求和,并取 k≈n/e,可保证成功概率至少约 1/e。这个结论依赖候选顺序是均匀随机排列。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 .