知识卡片

普通读书笔记卡 · 3605

雇用问题计数纪录更新

理解等级:中级

雇用问题每次面试都付低成本 cᵢ,仅当新候选胜过当前最佳才付高成本 cₕ。总费用取决于面试 n 次和“最佳纪录”更新 m 次,可写作 O(cᵢn+cₕm)。它把成本分析转为计数操作次数;最坏顺序质量递增时 m=n。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 5 章 5.1–5.2 节(`OEBPS/chapter005.xhtml`,文本字符 [0, 5000);公式图 Art_P245–P255)。 - 结论依据:5.1 节 HIRE-ASSISTANT 每名候选付面试成本,仅在超过当前 best 时另付雇用成本;严格递增的质量序列使 n 人都被录用。 - 原始内容:The hiring problem models how often a procedure updates its notion of which element is currently winning.