Learning Objectives
- 說明陣列的元素在記憶體裡連續存放，所以用索引讀取任何位置都是 O(1)
- 數出在最前面插入、刪除中間元素要搬動幾個元素，說明為什麼是 O(n)
- 說明動態陣列滿了以後怎麼長大：配置兩倍大的空間、把舊元素複製過去
- 用攤銷分析說明：雖然偶爾要複製很多元素，append 平均每次仍是 O(1)
- 對照 Python 串列、C++ vector、Java ArrayList 各種操作的成本
同樣是串列，有的操作快、有的慢
Python 的串列（list）、C++ 的 vector、Java 的 ArrayList，用起來都像「一排可以一直加東西的格子」。但同一個串列上的不同操作，速度可能差很多：
a = list(range(1_000_000))
x = a[500_000] # 很快
a.append(7) # 很快
a.insert(0, 7) # 慢：要搬動一百萬個元素
這一課要看清楚這些容器的底層，也就是陣列（array），並用上一課的方法數一數每種操作要做幾步：
| 操作 | 成本 |
|---|---|
用索引讀取或修改 a[i] |
O(1) |
| 在尾端加入（append） | 平均 O(1) |
| 在最前面或中間插入 | O(n) |
| 刪除最前面或中間的元素 | O(n) |
| 刪除尾端的元素 | O(1) |
看完這一課，你會知道表格裡每一格是怎麼來的。
陣列：一整排連續的格子
記憶體可以想成一長條、每一格都有編號（位址）的儲存空間。陣列的特色是：所有元素連續地放在一起，而且每個元素占的大小相同。
假設一個整數陣列從位址 1000 開始、每個整數占 4 個位元組（byte）：
| 元素 | a[0] | a[1] | a[2] | a[3] | … |
|---|---|---|---|---|---|
| 位址 | 1000 | 1004 | 1008 | 1012 | … |
所以要找 a[i]，不必從頭數過去，直接算：
a[i] 的位址 = 起點 + i × 每個元素的大小
不管 i 是 3 還是 300 萬，都只是一次乘法和一次加法，所以用索引讀取是 O(1)，叫做隨機存取（random access）：想看哪一格，就直接跳過去。
這裡的位址是說明用的數字。真正的位址由作業系統和執行環境決定，每次執行都可能不同；Python 的串列裡放的是指向物件的參考，但「參考」本身一樣是連續存放、大小相同，所以計算方式相同。
用索引讀取：直接算出位址
讀 a[0]、a[3]、a[7] 各只要算一次位址，步驟數一樣，不會因為索引比較大就比較慢。
在最前面插入：大家往後挪一格
「連續存放」帶來快速的讀取，也帶來代價：元素之間沒有空隙。要在最前面放一個新元素，就得把所有元素往後挪一格，空出第 0 格。
挪的時候要從最後一個開始往後搬：如果從前面開始，a[1] = a[0] 會把原本的 a[1] 蓋掉，後面就搬錯了。
n 個元素在最前面插入，要搬 n 次，所以是 O(n)。在索引 k 插入，要搬 k 右邊的 n - k 個元素；越靠前越慢，在尾端插入（而且還有空位）則完全不用搬。
在最前面插入 2
看格子裡的數字一個一個往右移：34 先搬到最後的空位，接著 21、13、8、5。5 個元素都搬完，第 0 格才空出來放 2。
刪除中間的元素：右邊的往左補
刪除也一樣。刪掉索引 k 的元素後會留下一個洞，陣列又不能有空隙，所以 k 右邊的元素要一個一個往左補，這次要從左邊開始搬。
要搬的個數是 n - 1 - k：刪第一個要搬 n - 1 個，刪最後一個完全不用搬。下面先刪索引 1，再刪最後一個，比較兩者的搬動次數。
刪除索引 1，再刪除最後一個
刪除索引 1 的 8 時，13、21、34、55 依序往左移一格，搬了 4 次。接著刪除最後一個元素，迴圈一次都不執行，搬 0 次。
三種語言的對應操作
內建的容器幫你做了上面的搬動，寫起來只有一行，但成本還在：
| 操作 | Python 串列 | C++ vector | Java ArrayList | 成本 |
|---|---|---|---|---|
| 讀取第 i 個 | a[i] |
a[i] |
a.get(i) |
O(1) |
| 尾端加入 | a.append(x) |
a.push_back(x) |
a.add(x) |
平均 O(1) |
| 刪除尾端 | a.pop() |
a.pop_back() |
a.remove(a.size() - 1) |
O(1) |
| 在最前面插入 | a.insert(0, x) |
a.insert(a.begin(), x) |
a.add(0, x) |
O(n) |
| 刪除最前面 | a.pop(0) |
a.erase(a.begin()) |
a.remove(0) |
O(n) |
| 找某個值在哪裡 | a.index(x) |
find(a.begin(), a.end(), x) |
a.indexOf(x) |
O(n) |
最後一列是線性搜尋（第 04 課）：陣列能用索引直接跳到某一格，但不知道某個值在哪一格，只能一個一個找。
如果程式常常要在最前面加入或移除（例如排隊），用陣列就不划算。第 10 課的雙向佇列（deque）和第 11 課的鏈結串列（linked list）在兩端加入、移除都是 O(1)，代價是失去用索引直接跳的能力。
想一想：搬動的成本
一個有 1,000 個元素的陣列，讀取 a[999] 和讀取 a[0] 相比？
這段程式會印出什麼？
a = [10, 20, 30, 40, 50, 60, 70]
n = 7
k = 2
moves = 0
for j in range(k, n - 1):
a[j] = a[j + 1]
moves += 1
print(moves, a[2])
程式用 a.pop(0) 一個一個取出串列最前面的元素，直到串列變空。串列一開始有 n 個元素，總共大約要搬動幾次？
陣列滿了怎麼辦：動態陣列
真正的陣列在建立時就決定了大小，不能原地變大，因為它後面那段記憶體可能已經被別的資料用掉了。那 Python 的串列為什麼可以一直 append？
因為串列是動態陣列（dynamic array）：它記得兩個數字，
- 大小（size）：現在放了幾個元素
- 容量（capacity）：底下這塊陣列總共有幾格
還有空位時，append 直接放進下一格。滿了的時候：
- 配置一塊兩倍大的新陣列
- 把舊陣列的元素一個一個複製過去
- 改用新陣列，再放入新元素
下面自己寫一個這樣的類別，從容量 1 開始放入 1～9，數一數總共複製了幾個元素。
容量加倍的動態陣列
放入 2、3、5、9 時空間剛好滿了，要換成兩倍大的 bigger，並把舊元素逐一複製過去（分別複製 1、2、4、8 個）。其他時候直接放進空格。9 次 append 總共只複製了 15 個元素。回到主程式的那幾步，看不到物件裡面的 data，所以視覺化會暫時顯示「還沒有這個變數」。
攤銷分析：偶爾很貴，平均很便宜
單看某一次 append，最壞要複製目前所有的元素，是 O(n)。但這種「貴的 append」很少發生，只在大小剛好是 1、2、4、8、16… 時出現。
把 n 次 append 的總成本加起來看。複製的次數是
1 + 2 + 4 + 8 + … + (不超過 n 的最大 2 的次方) < 2n
再加上每次放入元素本身的 n 步，n 次 append 總共不到 3n 步，平均每次不到 3 步。 這種「把偶爾很貴的成本平均分攤到每一次操作」的分析方法叫做攤銷分析（amortized analysis），我們說 append 的攤銷時間是 O(1)。Robert Tarjan 在 1985 年的論文〈Amortized Computational Complexity〉把這個分析方法系統化地整理出來。
為什麼一定要「加倍」？如果每次滿了只多加 4 格，就會每 4 次 append 複製一次全部元素，複製次數是 4 + 8 + 12 + … ，總共約 n²/8，又變回 O(n²)。下面的實作題會實際算給你看。
實際的容器也是這樣運作，只是細節由各語言的實作決定：Python 串列、C++ vector、Java ArrayList 每次長大的倍率都不一定是 2 倍，也不保證相同，所以不要寫依賴容量數字的程式。
如果事先知道大概要放多少元素，可以先預留空間，省下中途的複製：C++ 用 v.reserve(n)，Java 用 new ArrayList<>(n)。
想一想：動態陣列
用本課的動態陣列（容量從 1 開始、滿了就加倍），依序放入 17 個元素後，總共複製了幾個元素？
「append 的攤銷時間是 O(1)」的意思是？
實作：加倍與每次加 4 格
copies_doubling(n) 模擬「容量從 1 開始、滿了就加倍」，放入 n 個元素總共要複製幾次。請完成 copies_plus4(n)：容量從 4 開始，滿了就加 4 格（不是加倍），同樣回傳總複製次數。比較 n = 32 與 n = 1000 的結果。
重點整理
- 陣列的元素在記憶體裡連續存放、大小相同，
a[i]的位址 = 起點 + i × 元素大小，所以用索引讀取是 O(1) - 在最前面插入要把所有元素往後搬，刪除最前面要把所有元素往前補，都是 O(n)；越靠近尾端越便宜，尾端是 O(1)
- 陣列能用索引直接跳到某一格，但找某個值仍要一個一個看，是 O(n)
- 動態陣列（Python 串列、C++ vector、Java ArrayList）滿了就配置更大的空間並複製舊元素；容量加倍時，n 次 append 的總複製次數少於 2n
- 攤銷分析把偶爾很貴的操作平均分攤：append 的攤銷時間是 O(1)；如果每次只加固定幾格，總成本會變成 O(n²)
下一課：線性搜尋與二分搜尋。陣列找值要一個一個看，但如果陣列已經排好順序，就可以每次排除一半。