Learning Objectives
- 說明動態陣列的大小（size）與容量（capacity），以及它們必須維持的不變條件
- 實作容量滿了時「配置更大的陣列、搬移元素、釋放舊陣列」的擴充步驟
- 比較容量加倍與每次加固定格數，n 次 append 的總成本分別是 O(n) 與 O(n²)
- 用總和法與會計法說明 append 的攤銷時間是 O(1)
- 說明縮小容量要等到剩四分之一才縮的原因
- 說出 Python list、C++ vector、Java ArrayList 實際的成長方式，以及預留容量的寫法
陣列的容量是固定的，串列卻能一直加
上一課的陣列有一個硬限制：建立時就決定了容量，滿了就不能再插入。陣列也不能「原地變大」，因為它後面那段記憶體可能已經被別的資料占用。
可是 Python 的串列、C++ 的 vector、Java 的 ArrayList 都可以一直 append。它們都是動態陣列（dynamic array）：底下仍然是一塊固定容量的陣列，只是滿了的時候，換一塊更大的：
- 配置一塊更大的新陣列
- 把舊陣列的元素一個一個搬過去
- 釋放舊陣列，改用新的
動態陣列要記住三件事：
| 欄位 | 意思 |
|---|---|
data |
目前使用的那塊陣列 |
size |
已經放了幾個元素 |
capacity |
data 總共有幾格 |
不變條件：data[0..size-1] 是元素，size <= capacity；data[size] 以後的格子是預留的空位，裡面的值不算數。
這一課要回答一個問題：搬移的成本這麼高，為什麼大家都說 append 是 O(1)？
親手做一個動態陣列
容量從 2 開始。放入 30 時已經滿了，換成容量 4 的陣列，搬 2 個；放入 50 時又滿了，換成容量 8，搬 4 個。其他時候直接寫進 data[size]。最後 get(6) 的 6 雖然小於容量 8，但大於等於 size，那一格只是預留的空位，所以算超出範圍。C++ 版用 new int[...] 配置、delete[] 釋放舊的陣列，可以在右邊的「堆積」看到新的一塊出現、舊的一塊被釋放；Java 與 Python 的舊陣列沒有人再用，之後由垃圾回收處理。
每次要長多大
擴充一次要搬 size 個元素，是 O(n)。擴充得越少越好，但每次長太多又浪費空間。常見的兩種想法：
- 加倍（或乘上某個固定倍數）：容量 1、2、4、8、16……
- 每次加固定的 k 格：容量 k、2k、3k……
用「步數」來算 n 次 append 的總成本：每次寫入新元素算 1 步，擴充時每搬一個元素再算 1 步。
加倍時，擴充發生在 size 為 1、2、4、8……的時候，搬移的總數是
1 + 2 + 4 + … + (不超過 n 的最大 2 的次方) < 2n
再加上 n 次寫入，總成本不到 3n，是 O(n)。
每次加 k 格時，每 k 次 append 就擴充一次，搬移的個數是 k、2k、3k……，大約 n/k 項加起來：
k + 2k + 3k + … ≈ k × (n/k)² / 2 = n² / (2k)
總成本是 O(n²)。k 取大一點只是把常數變小，n 夠大時還是會被 n² 追上。下面讓兩種方式各 append 16 次，把每一次的成本畫成長條。
每一次 append 的成本
加倍時，大部分的長條都只有 1，偶爾出現一根高的（搬移），而且高的長條之間越隔越遠。每次加 2 格時，每隔一次就出現一根，而且越來越高。16 次的總成本，加倍是 31，每次加 2 格是 72；n 再變大，差距會越拉越開。
攤銷分析：看一連串操作的總成本
單看某一次 append，最壞要搬 n 個元素，是 O(n)。但這種「貴的 append」很少發生。 攤銷分析（amortized analysis）看的是一連串操作的總成本，再平均分給每一次操作。它不是機率上的平均，而是保證：任何順序的 n 次操作，總成本都不超過這個上限。
常見的兩種算法：
總和法（aggregate method）：直接把 n 次操作的總成本加起來再除以 n。上一段算過，加倍時總成本不到 3n，所以每次 append 的攤銷成本不到 3，是 O(1)。
會計法（accounting method）：想像每次 append 先收 3 枚代幣，實際成本是多少就付多少，多的存起來，之後搬移時拿出來用。
- 1 枚付給這一次的寫入
- 2 枚存起來：1 枚留給「之後擴充時搬自己」，1 枚留給「搬一個前半段的舊元素」（容量剛加倍時，前半段的元素已經把存款用掉了）
只要證明存款永遠不會變成負的，就表示收的 3 枚一定夠付所有的實際成本，所以每次 append 的攤銷成本是 3，O(1)。 這種分析方法由 Robert Tarjan 在 1985 年的論文〈Amortized Computational Complexity〉中系統化地整理出來。下面用程式模擬會計法，看存款的變化。
會計法：每次收 3 枚代幣
平常的 append 成本是 1，收 3 付 1，存款增加 2。擴充的那一次（第 2、3、5、9 次）成本比 3 高，就用存款補上。看長條：存款忽高忽低，但從來沒有變成負的，每次擴充完都還剩 3 枚。這就證明了每次收 3 枚夠用。
想一想：擴充與攤銷
動態陣列的容量從 1 開始、滿了就加倍。這段模擬會印出什麼？
cap, size, resizes = 1, 0, 0
for _ in range(20):
if size == cap:
cap *= 2
resizes += 1
size += 1
print(resizes, cap)
「append 的攤銷時間是 O(1)」是什麼意思？
如果動態陣列滿了以後每次只多 100 格，連續 append n 次的總成本是？
真實的 list、vector、ArrayList 怎麼長大
三種語言的內建動態陣列都依倍數成長，但倍數不同，而且是各實作自己的選擇，語言規格沒有規定。下表依各專案目前公開的原始碼整理：
| 實作 | 容量不夠時 | 大約的倍數 |
|---|---|---|
Python（CPython）的 list |
新容量＝需要的大小＋需要的大小 ÷ 8＋6，再調成 4 的倍數；原始碼註解列出的成長順序是 0、4、8、16、24、32、40、52、64、76…… | 約 1.125 倍 |
C++ vector（GCC 的 libstdc++） |
新容量＝目前大小＋max(目前大小, 要加的個數)，註解寫著「至少加倍」 | 2 倍 |
C++ vector（Microsoft 的 STL） |
新容量＝舊容量＋舊容量 ÷ 2 | 1.5 倍 |
Java ArrayList（OpenJDK 21） |
用預設建構子建立時先是空的，第一次加入時配置 10 格；之後新容量＝舊容量＋舊容量 ÷ 2 | 1.5 倍 |
倍數越大，擴充次數越少，但可能空著越多格；倍數小一點，空間比較省，擴充比較頻繁。只要是倍數成長，攤銷成本都是 O(1)。 這些數字隨版本可能改變，程式不要依賴容量的確切數值。
事先知道大概要放多少元素時，可以先預留容量，省下中途的搬移：
| 語言 | 寫法 |
|---|---|
| C++ | v.reserve(1000);；v.capacity() 可以查目前的容量 |
| Java | new ArrayList<>(1000) 或 list.ensureCapacity(1000) |
| Python | 沒有預留容量的方法；知道長度時可以直接 [0] * 1000 建好再填值 |
另外，C++ 的 vector 擴充時會把元素搬到新的一塊記憶體，原本指向元素的指標、參考、迭代器都會失效，擴充後不能再用。
刪除很多元素以後，要不要縮小
一直 pop 之後，容量可能遠大於元素個數，浪費記憶體。直覺的做法是「剩一半就縮成一半」，但這會出問題： 假設容量 8 剛好放滿 8 個，接下來 append、pop、append、pop 交替：
- append：滿了，擴充成 16，搬 8 個
- pop：剩 8 個，等於 16 的一半，縮成 8，又搬 8 個
- append：又滿了……
每一次操作都要搬 8 個，攤銷成本不再是 O(1)。這種在邊界上來回擴充、縮小的現象叫做震盪（thrashing）。
解法是讓兩個門檻拉開距離：滿了才加倍，但要剩四分之一才縮成一半。縮完以後容量剛好是元素個數的兩倍，離「滿」和「再縮」都還很遠，至少要再做很多次操作才會觸發下一次搬移。
剩一半就縮與剩四分之一才縮
同一串操作跑兩次。第一次「剩一半就縮」：每一次操作都觸發擴充或縮小，6 次操作搬了 48 個元素。第二次「剩四分之一才縮」：只有第一次 append 擴充，之後 size 在 8、9 之間來回，離 16 的四分之一（4）很遠，總共只搬 8 個。
想一想：會計法與縮小
會計法裡，每次 append 收 3 枚代幣。為什麼收 1 枚或 2 枚不夠？
動態陣列規定「剩一半就縮成一半」，在容量的邊界上 append、pop 交替做 n 次，總成本是？
依 OpenJDK 21 的原始碼，ArrayList 容量不夠時，新容量大約是舊容量的幾倍？
實作：會縮小的 pop
這個動態陣列的 resize 與 append 已經寫好（容量從 1 開始、滿了加倍）。請完成 pop：取出最後一個元素後把 size 減 1；如果 size 大於 0 而且不超過容量的四分之一，就呼叫 resize 把容量縮成一半。主程式放入 9 個元素（容量變成 16），再 pop 7 次，看容量什麼時候縮小。
重點整理
- 動態陣列底下是一塊固定容量的陣列，記錄
data、size、capacity；不變條件是data[0..size-1]為元素、size <= capacity - 滿了就配置更大的陣列、搬移元素、釋放舊陣列（C++ 用
new[]／delete[]）；索引只有 0～size-1 有效 - 容量依倍數成長，n 次 append 總成本 O(n)；每次只加固定 k 格，總成本 O(n²)
- 攤銷分析看一連串操作的總成本：總和法（總成本不到 3n），會計法（每次收 3 枚代幣，存款永遠不為負）；append 的攤銷時間是 O(1)
- 縮小要等到剩四分之一才縮成一半，避免在邊界來回震盪
- CPython 的 list 約 1.125 倍、GCC 的 vector 2 倍、Microsoft 的 vector 與 Java 的 ArrayList 1.5 倍；知道大小時用
reserve、new ArrayList<>(n)預留容量
下一課：環狀佇列與雙端佇列。用陣列做佇列時，從前面取出元素會留下空位；下一課讓 front 與 rear 繞著陣列轉圈，不必搬移任何元素。