【算法分析与设计】第25篇：在线算法与竞争比分析
到目前为止，本专栏讨论的所有算法都共享一个默认前提：在执行开始之前，整个输入数据完整可用。排序算法知道你即将排序的全部数字，最短路径算法拥有整张图的拓扑与边权。这种“全知全能”的算法称为离线算法。然而，一旦走出教科书，这个假设往往瞬间崩塌。操作系统在决定换出哪个内存页面时，无法预知进程接下来要访问哪个地址；投资经理在今天调仓时，看不到下周的市场行情；自动驾驶的路径规划器不可能提前获取前方突发的障碍物信息。在这些场景中，输入是逐片到达的，算法必须在每一片信息到达后立即做出决策，且决策一旦生效便不可撤销。这一类算法被称为在线算法，对应的理论度量工具称为竞争比分析。
一、在线问题的形式化定义
在线问题的输入可以建模为一个有限序列 σ=(σ1,σ2,…,σn)σ=(σ1,σ2,…,σn)。在第 tt 步，算法仅观察到前缀 (σ1,…,σt)(σ1,…,σt)，必须基于这些有限信息立即输出一个决策 atat，且无法在未来反悔或修正。第 tt 步产生的代价 ct(at,σt)ct(at,σt) 即时发生并计入总代价。序列的长度 nn 可能事先已知，也可能未知。
与之对应，离线算法 OPT 事先通晓整个序列 σσ，可以以全局最优的方式统筹决策。记 ALG(σ)ALG(σ) 为在线算法在处理输入 σσ 时产生的总代价，OPT(σ)OPT(σ) 为离线最优算法在同样输入上的总代价。
竞争比是在线算法性能的核心度量指标。若存在常数 ρ≥1ρ≥1 和常数 cc，使得对任意输入序列 σσ，均有：
ALG(σ)≤ρ⋅OPT(σ)+cALG(σ)≤ρ⋅OPT(σ)+c
则称该在线算法为 ρρ-竞争的，ρρ 为竞争比。常数 cc 用于吸收小规模输入上两者的固定差异，不影响渐进分析。竞争比的直观含义是：无论输入序列多么恶毒，在线算法的代价始终不超过离线最优代价的 ρρ 倍（加上一个常数）。换言之，竞争比衡量的是“因无法预知未来而付出的额外代价的最坏情况上限”。
二、滑雪板租用：经典入门案例
滑雪板租用问题是最简洁的在线决策模型：你决心开始滑雪，但不知道自己会滑多少次。每租一次滑雪板需花费 11 单位，而直接购买一副滑雪板需花费 BB 单位（B≫1B≫1）。每次去滑雪前，你必须决定是租还是买——一旦买下，后续不再需要支付租金。你不知道自己会滑多少次雪，决策需在线进行。
这个问题只有两种确定性策略：要么一直租，要么在某一次直接买。
若一直租：输入为滑 kk 次，总代价 kk。但若 k≫Bk≫B，离线最优策略是在第一次就买（代价 BB），竞争比可任意大。
若在第 tt 次购买：最坏情况是 t=Bt=B，即刚好在租金累积到 BB 时买下。此后若再滑任何次数，总代价 B+(后续租金0)B+(后续租金0) 与 OPT 相同；若实际只滑 B−1B−1 次，代价为 (B−1)+B=2B−1(B−1)+B=2B−1，而 OPT 只需 B−1B−1（全租），比值约 22。
由此得到确定性策略的竞争比下界为 2−1/B2−1/B，且“前 B−1B−1 次租，第 BB 次买”这一策略恰好达到该下界——既不过早买到不需要的东西，也不过晚支付过多租金。
随机化改进：若允许算法掷硬币来决定何时购买，可以突破确定性的 22 下界。策略设计为：以递减的概率分布决定在哪一天购买，使得在任何 kk 下，期望总代价与 OPT 的比值均控制在 e/(e−1)≈1.582e/(e−1)≈1.582 以内。这一上界同时也是随机化在线策略的严格下界——任何随机化算法的最坏情况期望竞争比不可能更优。
三、页面置换：缓存管理的在线模型
操作系统在管理虚拟内存时面临一个经典在线决策：缓存最多容纳 kk 个页面，当发生缺页而缓存已满时，必须换出一个页面，为新页面腾出空间。请求序列 σ=(p1,p2,…,pn)σ=(p1,p2,…,pn) 在线到达，算法每次只能看到当前及过去的请求，换出决策不可撤销。
此问题的离线最优解由Belady在1966年给出：当必须换出时，选择未来最远才被访问的页面。这一策略基于全知视角，物理上不可实现，但它提供了OPT的代价基准。
确定性在线策略中最著名的是：
LRU（最近最少使用）：换出最近一次访问时间距今最久的页面。
FIFO（先进先出）：换出最早进入缓存的页面。
LFU（最不频繁使用）：换出历史访问次数最少的页面。
所有这些确定性策略的竞争比至少为 kk——因为攻击者可以构造一个请求序列，使得在离线最优仅发生 11 次缺页的情况下，在线策略发生 kk 次缺页。事实上，任何确定性在线页面置换算法的竞争比下界就是 kk，而LRU和FIFO均达到 kk 的竞争比。
标记算法与随机化突破：标记算法将请求序列划分为若干“阶段”，每阶段中首次访问一个页面时做标记，阶段内最多允许 kk 个不同页面。随机化标记算法——在必须换出时从该阶段未被标记的页面中随机选取一个——可以达到约 2lnk2lnk 的竞争比，显著优于确定性的 kk。这一改进在缓存容量 kk 较大时尤为显著。
四、确定性下界与随机化的力量
从滑雪板租用到页面置换，我们反复看到同一个现象：确定性在线算法的竞争比下界，往往能被随机化策略严格突破。这并非偶然。
确定性的下界构造依赖一个“恶意对手”模型：对手在观察到算法的确定性行为后，动态调整后续输入，使算法永远做出最差选择。这种对手称为自适应离线对手。在线算法的理论研究区分几种不同能力的对手模型：
遗忘式对手：在算法开始前就固定整个输入序列，不随算法的随机选择而改变。随机化算法通常在此模型下分析。
自适应对手：可根据算法过去的行为和输出动态调整后续输入，但不能观测算法的内部随机硬币。
随机化之所以能突破确定性下界，本质上是因为概率分布使得对手无法精确预测算法的行为，从而削弱了恶意构造输入的能力。这在理论上是随机性增强算法能力的最清晰体现之一。
五、竞争比分析的方法论意义
竞争比分析将在线算法设计从一个“经验调参”的问题提升为具有严格数学保证的理论框架。竞争比 ρρ 提供了一个跨输入的统一性能保证——无论输入序列怎样，成本不会超过 ρ⋅OPT+cρ⋅OPT+c。这一特性在安全关键的实时系统中尤为重要：工程师需要知道，即使在最坏情况下，在线调度器的性能不会无限劣化。
当然，竞争比分析也受到一些批评。最坏情况的视角可能过于悲观，在某些应用中，典型输入远非最坏情况，平均情况性能才是真正关心的指标。此外，竞争比为常数的前提通常要求问题具有某种可比较性——某些在线问题（如在线装箱）在确定性和随机化下的竞争比可随输入规模发散。这些讨论将我们引向更精细的在线算法分析模型，如在线学习中的遗憾界分析，这已属于进阶专题的范畴。
六、总结与展望
在线算法研究在“不确定性下决策”这一根本挑战中建立了严谨的理论。竞争比提供了一个优雅而强大的度量工具，使得我们能够严格论证一个在线策略的优劣，而不仅仅是经验性地宣称“这个方法效果不错”。从滑雪板租用的 e/(e−1)e/(e−1) 到页面置换的 O(logk)O(logk)，随机化一再展现出突破确定性壁垒的能力。
下一篇，我们将目光转向另一类处理NP困难问题的精细策略——参数化算法。不同于近似算法牺牲解的精度、随机化算法牺牲确定性，参数化算法将问题的“困难”隔离在某个参数上，当该参数较小时，即使输入规模很大，仍能在指数时间——但指数底仅依赖于该参数而非输入规模——内求出精确最优解。固定参数可解性理论为处理NP困难问题提供了一条与近似和随机化正交的路径。