資料結構›Ch2 陣列與字串
第 2 題/共 6 題
◀ DS 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 kk costs Θ(k)\Theta(k). Which statement is true when considering nn insertion and removal operations?

📄 台大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch2 陣列與字串
本章題號 · 1–6 / 6