2016/11/11 Algorithm

今天繼續上ch17 Amortized Analysis
17.4 Dynamic Table
這節主要講一個動態的陣列, 它的容量會隨儲存量的多寡, 而有size上的自動變化
雖然看起來這種"動態"好像要花不少時間,
但它可以證明, 透過本章的"先付款"方法
(假設中線是最prefer的狀態, 超過中線付$2, 低於中線付$1)
可以控制每一步成本約是O(1),
其中Insert的成本小於等於3, Delete的成本小於等於2
而存款永遠都是正的(圖Figure 17.4)