知识卡片
在线算法逐步接收输入
在线算法边接收请求边决策,事前不知道完整输入;
离线算法则可先看全体输入再求解。
评价在线决策时,应把未知未来视为信息约束,而非实现细节。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第27章 在线算法 · 查看原书依据
An online algorithm receives its input progressively over time, rather than having the entire input available at the start, as in an offline algorithm. Online algorithms pertain to many situations in which information arrives gradually. A stock trader must make decisions today, without knowing what the prices will be tomorrow, yet wants to achieve good returns. A computer system must schedule arriving jobs without knowing what work will need to be done in the future.
参考来源
- 位置:《算法导论(第4版)》第27章《在线算法》(OEBPS/chapter027.xhtml,文本字符[0,5000))。
- 结论依据:原文定义在线决策或竞争比,并用电梯和搜索链表示例给出适用条件与成本。
- 原始内容:An online algorithm receives its input progressively over time, rather than having the entire input available at the start, as in an offline algorithm . Online algorithms pertain to many situations in which information arrives gradually. A stock trader must make decisions today, without knowing what the prices will be tomorrow, yet wants to achieve good returns. A computer system must schedule arriving jobs without knowing what work will need to be done in the future.