页面置换算法和竞争性分析 Posted on 2019-08-05 | In Algorithm 竞争性分析竞争性分析(Competitive Analysis)是分析在线算法的有用技术。对于在线算法 $A$,设 $C_A(S)$ 表示算法 $A$ 在输入序列 $S$ 上的开销。如果存在 $k$ 对于任意的序列 $S$ 都满足 其中 $OPT(S)$ 是离线最优算法的开销,那么称算法 $A$ 是 $k$-Competitive 的。 Read more »