在线算法

概述

在线算法 是必须在看到全部输入之前就做出决策的算法，与可以预先看到完整输入的离线算法形成对比。

定义

在线算法

在线算法是一种必须逐步处理输入序列的算法：在每个步骤，算法必须基于当前已知的输入做出不可撤回的决策，而无法预知未来的输入。

核心性质

• 与离线算法对比：离线算法可以预先看到全部输入后做全局最优决策；在线算法只能基于局部信息决策
• 竞争分析：在线算法的性能通过竞争比衡量——算法代价与最优离线算法代价之比的最坏情况上界
• 典型问题：页面置换（缓存淘汰）、在线装箱、负载均衡、在线排序等
• 实际意义：许多现实场景天然是在线的，如操作系统内存管理、网络路由、实时调度等
• 局限性：在线算法通常无法达到离线最优解的质量，竞争分析量化了这一差距

章节扩展

第1章：在线算法展示了算法设计的另一维度——在信息不完全条件下的决策。页面置换问题将在后续章节中讨论。

参见

• 1.1 算法 — 算法的分类与模型