在线算法
在线算法
本章内容在线算法基本概念页面调度问题
本章内容 ◼ 在线算法基本概念 ◼ 页面调度问题 2
在线算法基本概念前面介绍的算法口在算法执行之前整个输入数据实际应用存在不满足上述条件的情况磁盘调度问题操作系统的页面调度问题Datastreams?
在线算法基本概念 ◼ 前面介绍的算法 在算法执行之前整个输入数据 ◼ 实际应用存在不满足上述条件的情况 磁盘调度问题 操作系统的页面调度问题 Data streams 3
在线算法基本概念竞争比设在线算法代价为A，离线最优算法代价为OPT若存在非负常数α和c，使得A≤α·OPT+C，则称α为该在线算法的竞争比（α-competitive)当在线算法的竞争比不可能再改进时，称其为最7优在线算法
在线算法基本概念 ◼ 竞争比 设在线算法代价为𝑨，离线最优算法代价为𝑶𝑷𝑻 ， 若存在非负常数 𝜶 和 𝒄 ，使得𝑨 ≤ 𝜶 ∙ 𝑶𝑷𝑻 + 𝒄， 则称 𝜶 为该在线算法的竞争比 (𝜶-competitive) 当在线算法的竞争比不可能再改进时， 称其为最 优在线算法 4
页面调度问题问题：高速缓存可放k个页面：低速内存有多个页面给定一个页面请求序列< p1,P2,…,Pn>，当高速缓存占满的情况下，在高速缓存出现页面缺失时，选择哪个页面与低速内存页面交换，使得遇到缺失的次数最少5
页面调度问题 ◼ 问题： 高速缓存可放k个页面；低速内存有多个页面 给定一个页面请求序列< 𝒑𝟏,𝒑𝟐,⋯ ,𝒑𝒏 >，当高速 缓存占满的情况下，在高速缓存出现页面缺失时， 选择哪个页面与低速内存页面交换，使得遇到缺失 的次数最少 5