線上演算法
理論
定義 1： 一個優化問題 Π由一組的情況下， ＆Sigma; Π 。對於每一個例項σ∈Σ Π 有一組Ζ σ 的解決方案和一個目標函式 ˚F σ ：Ζ σ →交通ℜ ≥0 其中分配 apositive 真實值的每一個的解決方案。
我們說 OPT（σ）是最優解的值，A（σ）是演算法 A 對於問題Π和 w A （σ）= fσ （A（σ））其值的解。
定義 2： 最小化問題的線上演算法 A 如果存在常數τ∈ℜ，則競爭比率 r≥1
w A （σ）= fσ （A（σ））≤r⋅OPT（＆sigma）+τ
所有例項σ∈Σ Π 。A 稱為 r 競爭線上演算法。甚至
w A （σ）≤r⋅OPT（＆sigma）
所有例項σ∈Σ Π 則稱 A 是一個嚴格的 R-競爭力的線上演算法。
命題 1.3： LRU 和 FWF 是標記演算法。
證明： 在每個階段的開始（第一個階段除外）， FWF 具有快取未命中並清除快取。這意味著我們有 k 個空頁面。在每個階段都要求最多 k 個不同的頁面，因此在階段期間將會出現逐出的情況。所以 FWF 是一種標記演算法。
讓我們假設 LRU 不是標記演算法。然後有一個例項σ，其中 LRU 在階段 i 中被標記的頁面 x 被驅逐。讓σ 噸 在階段 I，其中 x 被逐出該請求。由於 x 被標記，因此在同一階段中 x 必須有較早的請求σt * ，因此 t * <t。T *之後，x 是最新的快取頁面，所以要在 t 序列σ得到了拆遷戶 T * + 1 ，…，σ ŧ 必須從 x 個不同的頁面請求至少 k。這意味著階段 i 已經請求至少 k + 1 個不同的頁面，這與階段定義相矛盾。因此 LRU 必須是標記演算法。
命題 1.4： 每個標記演算法都是嚴格的 k 競爭性。
證明： 設σ是尋呼問題的例項和σ的相位數。當 l = 1 則則每個標記演算法都是最優的並且最優離線演算法不能更好。
我們假設 l≥2。例如σ的每個標記演算法的成本是從上面用 l·k 限制的，因為在每個階段中，標記演算法在不驅逐一個標記頁面的情況下不能超過 k 個頁面。
現在我們試圖表明，最優離線演算法在第一階段中為σ，k 驅逐了至少 k + 1-2 頁，並且除了最後一階段之外每個後續階段至少有一個。為了證明，我們定義σ的 l-2 析取子序列。子序列 i∈{1，…，l-2}從階段 i + 1 的第二個位置開始，並以階段 i + 2 的第一個位置結束。
設 x 為階段 i + 1 的第一頁。在子序列 i 的開始處，在最佳離線演算法快取記憶體中存在頁面 x 和至多 k-1 個不同頁面。在子序列中，我的 k 頁面請求與 x 不同，因此最佳離線演算法必須為每個子序列驅逐至少一頁。由於在階段 1 開始快取仍為空，因此最佳離線演算法在第一階段期間導致 k 驅逐。這表明了這一點
w A （σ）≤l⋅k≤（k + l-2）k≤OPT（σ）·k
推論 1.5： LRU 和 FWF 是嚴格 K-競爭力。
對於線上演算法 A 是否具有競爭力，我們稱之為 A 不具有競爭力。
命題 1.6： LFU 和後進先出法是沒有競爭力。
證明： 設 l≥2 常數，k≥2 快取大小。不同的快取頁面是 nubered 1，…，k + 1。我們看看以下順序：
第 1 頁要求第 1 頁，而不是第 2 頁，因此要求第 1 頁。最後，對頁面 k 和 k + 1 存在（l-1）交替請求。
LFU 和 LIFO 用 1-k 頁填充快取。當請求頁面 k + 1 時，頁面 k 被逐出，反之亦然。這意味著子序列（k，k + 1） l-1 的 每個請求都會驅逐一頁。此外，它們是第一次使用第 1-（k-1）頁時的 k-1 快取未命中。所以 LFU 和 LIFO 逐出大致的 k-1 + 2（l-1）頁面。
現在我們必須證明，對於每個常數τ∈ℜ和每個常數 r≤1，存在一個 l
等於
為了滿足這種不相等，你必須選擇足夠大的。所以 LFU 和 LIFO 沒有競爭力。
命題 1.7： 有沒有 R-中的競爭與尋呼確定性線上演算法 [R <K 。
來源
基本材料
- 指令碼線上演算法（德語），Heiko Roeglin，波恩大學
- 頁面替換演算法
進一步閱讀
- Allan Borodin 和 Ran El-Yaniv 的線上計算和競爭分析