知识卡片

普通读书笔记卡 · 3678.a.3.b.1.a.1

随机标记期望竞争比为对数级

理解等级:高级

设时期 i 有 r_i 个相对时期 i−1 的新块,离线最优在这两个时期共见到 k+r_i 个不同块,而缓存只能放 k 个,因此其失误数满足 m_{i−1}+m_i≥r_i。把相邻时期的不等式相加,每个 m_i 至多被计两次,得到 Σr_i≤2Σm_i。

随机标记在时期 i 的期望失误至多 r_iH_k,故总期望失误至多 H_kΣr_i≤2H_kΣm_i。由于 H_k=Θ(log k),其期望竞争比至多 2H_k=O(log k)。

此结论针对遗忘型对手,即请求序列不能根据算法当次的随机选择自适应改变。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第27章 在线算法 · 查看原书依据

      No matter what the cache contents were at the beginning of epoch i − 1, after k + ri distinct requests, there must be at least ri cache misses. There could be more, but there is no way to have fewer. Letting mi denote the number of cache misses of the

    参考来源

    - 位置:《算法导论(第4版)》第27章《在线算法》(OEBPS/chapter027.xhtml,文本字符[50000,55000))。 - 结论依据:原文证明 `m_{i−1}+m_i≥r_i`,并由 `Art_P886.jpg`–`Art_P888.jpg` 的总期望上界与离线下界推出竞争比至多 `2H_k`。 - 原始内容:No matter what the cache contents were at the beginning of epoch i − 1, after k + r i distinct requests, there must be at least r i cache misses. There could be more, but there is no way to have fewer. Letting m i denote the number of cache misses of the