程式設計面試：如何實作動態陣列並證明 append 的攤銷 O(1)？
題目與適用情境
請使用固定陣列實作支援 get(index)、set(index, value) 與 append(value) 的動態陣列。陣列已滿時擴容，要求說明成長策略、邊界行為、append 的最壞時間與攤銷時間，並比較線性擴容和幾何擴容。
題目假設元素是參照或固定大小的值，索引從 0 開始；越界存取拋出例外，空陣列允許 append。公開面試題庫把動態陣列/Vector 與 Microsoft、記憶體管理和攤銷分析連結；MIT 6.006 講義則將動態陣列的尾端插入列為攤銷 Θ(1)。
面試官考察什麼
- 是否區分
size與capacity，並維護「有效元素都在前 size 個槽位」的不變量。 - 是否選擇幾何成長，而不是每次只增加一個槽位。
- 是否能用總複製量、會計法或勢能法證明攤銷界，而不是只背 O(1)。
- 是否說明空容量、整數溢位、記憶體失敗、縮容和中間插入的邊界。
回答前需要先確認的問題
- 只要求尾端 append，還是也要支援中間 insert、delete 和 pop？後者會改變複雜度。
- 元素是否固定大小？是否需要保留參照語意、迭代器失效規則或執行緒安全？
- 擴容目標是降低複製次數、節省空間，還是滿足即時延遲上限？
- 是否要求 shrink？若要求，觸發門檻是否與擴容門檻分離以避免抖動？
30 秒回答架構
我會保存底層陣列、size 與 capacity。append 有空槽時直接寫入；已滿時配置更大的陣列、複製前 size 個元素，再寫入新值。成長應使用固定倍數，例如翻倍：第 n 次擴容複製的總元素數是一個幾何級數，小於 2n，因此 n 次 append 的總成本是 O(n)，單次攤銷 O(1)。單次擴容仍是 O(n)，不能說每次最壞 O(1)。
分步深入解答
狀態與不變量
維護三個欄位：底層陣列 data、有效元素數量 size、配置槽位數量 capacity。始終滿足 size 不小於 0 且不大於 capacity，有效元素位於索引區間 [0, size)；append 只寫入 data[size] 並把 size 加一。get 和 set 只允許存取 [0, size)，不能把尚未初始化的容量當作元素。
幾何擴容策略
當 size == capacity 時，配置至少 max(1, capacity * 2) 的新陣列，複製舊元素並替換參照。初始 capacity 為 0 時要特殊處理，否則乘二仍是 0。翻倍讓兩次擴容之間至少有與目前規模同數量級的廉價 append；成長因子越大，複製頻率越低但閒置空間越多。
~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;
public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }
public int size() { return size; }
public Object get(int index) { check(index); return data[index]; }
public void set(int index, Object value) { check(index); data[index] = value; }
private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~
這裡的 Object[] 只是展示泛型抹除下的常見實作；正式程式仍要決定 null、記憶體配置失敗和併發存取語意。核心不變量與複雜度不依賴 Java。
攤銷證明
假設 capacity 從 1 開始翻倍，連續 append n 個元素。普通寫入貢獻 n 次常數成本；擴容複製發生在容量 1、2、4、8……時，總複製量低於 2n。因此總成本小於 3n 加初始化常數，n 次操作的平均成本是 O(1)。
這是對一段最壞操作序列的保證，不是輸入隨機時的平均值。某次剛好觸發擴容時仍需複製 Θ(n) 個元素，因此單次最壞時間是 O(n)，get/set 的最壞時間是 O(1)，空間是 O(n)。
線性成長與縮容
如果每次只增加 c 個槽位，插入 n 個元素會複製約 c + 2c + ... 的線性級數，總成本為 Θ(n²)，append 的攤銷時間退化為 Θ(n)。幾何成長通常更合適，但成長因子越大，峰值閒置空間越高。
若支援 pop，可以在 size/capacity 低於門檻時縮容；擴容門檻和縮容門檻必須分開，例如已滿時翻倍、低於四分之一時減半，避免「加一個、刪一個」在邊界反覆搬遷。縮容不會改變尾端操作的攤銷 O(1)，但會增加釋放與複製的暫停成本。
可驗證的邊界
測試空陣列第一次 append、容量剛好已滿時的 append、連續擴容、重複參照、負索引、index 等於 size、超大容量溢位和配置失敗。用受控的複製計數器驗證 n 次 append 的總複製量與 n 成正比；不要只測最後陣列內容，因為線性擴容也能產生正確結果。
高品質示範回答
我會分開維護底層陣列、size 和 capacity，並保證有效元素永遠位於前 size 個位置。append 有空槽時直接寫入；已滿時配置兩倍容量、複製舊元素再寫入。初始容量為零時至少配置一個槽位。
翻倍的關鍵是攤銷證明：連續 n 次 append 的擴容複製量低於 2n，再加 n 次常數寫入，總成本 O(n)，所以 append 攤銷 O(1)。但觸發擴容的那次最壞仍是 O(n)，不能把攤銷界說成每次呼叫的硬延遲上限。線性成長會造成總複製 Θ(n²)；若支援縮容，我會使用滯後門檻避免抖動，並測試空輸入、越界、溢位和配置失敗。
常見錯誤
- 每次已滿只加一個槽位 → 複製次數形成平方級總成本 → 使用幾何成長並給出級數證明。
- 把 append 說成最壞 O(1) → 忽略擴容時的複製 → 明確區分單次最壞 O(n) 與序列攤銷 O(1)。
- 用 capacity 判斷 get 是否有效 → 讀到未初始化槽位 → 用
index不小於 0 且小於 size 驗證。 - 初始 capacity 為零時直接乘二 → 陣列永遠無法成長 → 使用至少一個槽位的特殊分支。
- 低水位立即縮容 → 交替 append/pop 造成反覆搬遷 → 分離擴容與縮容門檻。
追問與應對
如果要求每次 append 都有 O(1) 最壞時間怎麼辦？
普通連續陣列擴容會產生 O(n) 搬遷，不能承諾每次硬上限。可以使用分段陣列、增量搬遷或預先配置上界，但會犧牲連續記憶體、索引常數或空間；先確認延遲目標是否真的要求 worst-case。
成長因子從 2 改成 1.25 會怎樣？
只要成長因子嚴格大於 1，尾端 append 仍可攤銷 O(1)，但複製更頻繁、額外空間更少。成長因子接近 1 時常數項變大；選擇應結合記憶體預算、配置器行為與延遲目標，而不是只比較 Big-O。
如何證明線性成長是 O(n²)？
每次擴容只增加 c 個位置時，第 j 次擴容約複製 jc 個元素；前 n 個元素約需 n/c 次擴容，複製總和是 c + 2c + ... + (n/c)c = Θ(n²)。因此每次 append 的攤銷成本是 Θ(n)。
支援中間 insert 後複雜度如何變化？
即使容量充足，中間插入也要把後綴元素右移，最壞 O(n)。擴容複製只是額外成本；動態陣列的優勢仍是隨機存取和尾端操作，不應把所有 insert 都歸為 O(1)。
多執行緒同時 append 如何處理？
需要鎖、單一執行緒 owner 或原子索引加安全擴容協定。只把 size 宣告為原子並不能保護「檢查容量、配置、複製、替換」整段；若題目沒有併發要求，應先明確限定單執行緒邊界。