動態陣列的加倍擴容（table doubling）

普通陣列大小固定，但你常想要一個按需成長的串列——一個一個推入項目而不知最終數量。動態陣列（vector、ArrayList、Python list 背後的引擎）的做法是保有一塊固定大小的記憶體，當它填滿時，配置一塊更大的並把所有東西複製過去。加倍擴容就是「每次填滿就把新區塊做成兩倍大」的策略，它是攤還分析解釋驚人效率的教科書範例。

從容量 1 開始做 n 次附加的機制如下。大多數附加只是寫入空格，O(1)。但每當陣列滿了，一次附加會先配置一個容量加倍的新陣列並把所有現有元素複製過去——這是 O(目前大小) 的步驟。擴容發生在大小 1、2、4、8、...直到 n，所以複製工作總計 1 + 2 + 4 + ... + n/2，小於 n。簡單寫入總計 n。所以 n 次附加加起來花不到 2n，每次附加的攤還成本是 O(1)，即使單一次擴容附加花 O(n)。你能用三種方式證明：聚合（把上面的等比級數加總）、記帳（每次附加收 3，在每個新元素上存 2 以預付它日後的複製）、或位勢（Phi = 2*大小 - 容量）。

加倍使動態陣列實用，而因子 2 並非魔法——任何大於 1 的常數成長因子（1.5 很常見）都給出攤還 O(1)，因為擴容成本仍構成等比級數。誠實的警告：以固定「加法」量成長（例如每次 +10 格）會摧毀這個界，使附加成為攤還 O(n)；加倍在剛擴容後可能浪費掉多達一半的配置記憶體；而單一次附加在最壞情況下仍花 O(n)，所以當每個個別操作都必須快時（如硬即時系統），動態陣列並不合適。