資料結構›Ch2 陣列與字串第 2 題/共 6 題
2. Amortized Analysis、Dynamic Array
#DS-02-002中Amortized AnalysisDynamic Array
Consider a dynamic table that: (1) starts empty with capacity 1; (2) doubles its capacity when full; (3) shrinks its capacity by a factor of 1/2 when the capacity >= 4 and the number of stored elements falls below one quarter of the capacity. Assume that inserting or deleting an element costs 1, and resizing a table of size costs . Which statement is true when considering insertion and removal operations?
參考答案與解析
答案 (D):這是 CLRS 動態表格的經典結論——用「容量剩 1/4 才縮小成一半」這個門檻,配合位能法可以證明每個操作攤還 O(1)。但如果改成「剩一半就縮小成一半」,會出現「震盪」問題:在門檻附近反覆插入、刪除會不斷觸發整個表格的搬移,攤還成本會退化到 Θ(n),無法再維持 O(1)。這正是教科書用來說明「縮小門檻要夠保守」的經典陷阱。(A)(B)(C)(E) 皆與此結論矛盾,錯誤。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch2 陣列與字串