Online算法（差別于offline 算法）的3個特點：
- 基于部分的input，隻知道目前和過去的，并不知道未來的input
- 相當于在現有input的基礎上用貪心算法（local gready）
- 從全局來看并不是最優，因為不能對global data做出accurate assumption
為了分析online算法，我們引入霸氣牛逼吊炸天的 competitive analysis技術。 那麼拿online算法的cost和誰比呢？那必然是和上帝視角的offline算法，最優的cost，C_opt。 如果一個online算法A滿足下面：
那我們就說，算法A是K-competitive的，意思就是A的cost不超過（offline opt 的乘以K，再加個常數）。 其實competitive analysis也是一種amortized analysis, 隻不過它算的不是簡單的amortized cost, 而是相對的，相對于（offline opt）。
舉個栗子，Move-To-Front, 一種update linked list中元素排序的方法，使得總access cost變小。 Offline opt 有static(元素位置不能改變) 和dynamic(元素位置可以改變)兩種version. 可以嘗試分析一下，static還可以，dynamic特别酸爽。
Paging算法 假設有cache（容量小）和main memory(容量大) 兩級的memory系統。CPU要處理的時候，是從cache讀入data的。 是以要是能把CPU較為常用的data放在cache裡就能節省時間，但是cache比較小，是以就得決定什麼内容放cache。 CPU在cache裡面找一個page, 沒找到，就叫page fault。我們的目标：減小page fault. cache容量有限，有進就有出，如果需要discard一些page, 我們有一些政策： FIFO，或者least recently used, 或者least frequently used. 相對應的offline opt上帝視角開挂法就是：size k = 3
