動態陣列擴容策略:當陣列滿時,容量加倍。
單次 Push 成本:
- 一般情況:O(1)(直接寫入)
- 擴容時:O(n)(複製所有元素)
平攤分析:n 次 push 的總成本 ≤ 3n
- 每個元素最多被複製 log(n) 次
- 平攤成本 = O(1)
三種分析方法:聚合分析、記帳法、勢能法