知识卡片

普通读书笔记卡 · 3624.a.1.b.1.a

排序后活动选择线性扫描

理解等级:中级

活动按结束时间排好后,递归选择器从当前活动之后寻找首个开始时间不早于当前结束时间的候选,选中后递归处理剩余活动。

各活动在所有递归调用中只受一次扫描检验,所以选择阶段为线性时间;预排序另需成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第15章 贪心算法 · 查看原书依据

      Assuming that the activities have already been sorted by finish times, the running time of the call RECURSIVE-ACTIVITY-SELECTOR (s, f, 0, n) is Θ(n). To see why, observe that over all recursive calls, each activity is examined exactly once in the while loop test of line 2.

    参考来源

    - 位置:《算法导论(第4版)》第 15 章《贪心算法》(`OEBPS/chapter015.xhtml`,文本字符 [10000, 15000))。 - 结论依据:原文给出递归选择器的扫描方式,并把线性界限定在已按结束时间排序的输入上。 - 原始内容:Assuming that the activities have already been sorted by finish times, the running time of the call R ECURSIVE -A CTIVITY -S ELECTOR ( s , f , 0, n ) is Θ( n ). To see why, observe that over all recursive calls, each activity is examined exactly once in the while loop test of line 2.