跳轉到

2.1 動態陣列的原理#

概念說明#

靜態陣列在建立時就要宣告固定長度，但大多數應用不知道資料會有多少。動態陣列（dynamic array） 解決了這個問題：它內部其實維護一塊「容量（capacity）」大於「長度（size）」的固定陣列，當長度追上容量時，就配置一塊更大的新陣列（通常是兩倍），把舊元素全部搬過去，再釋放舊陣列。Python 的 list、C++ 的 vector、Java 的 ArrayList 都採用這個策略。

為什麼要「加倍」而不是「每次多一格」？若每次只多一格，插入 n 個元素共需 1+2+…+n = O(n²) 次搬移；每次加倍，搬移總次數為 1+2+4+…+2^k ≤ 2n = O(n)，平均到每次操作只要 O(1)。這就是攤攤（amortized）O(1) 的由來。

操作步驟#

以自製的 DynArray 為例，各操作的流程：

  1. append(x)：若 size == capacity，先 _resize(2 * capacity)；再把 x 放到第 size 格，size += 1。
  2. _resize(new_cap)：配置長度 new_cap 的新陣列，把舊的 size 個元素逐一複製過去，替換內部引用。
  3. insert(i, x)：先確認容量，再把索引 i 之後的元素由後往前逐一右移一格，最後放 x。
  4. remove(i)：把索引 i 之後的元素由左往右逐一左移一格覆蓋，size -= 1；若 size 低於容量的四分之一，可縮容一半以節省記憶體。

Python 實作#

class DynArray:
    def __init__(self):
        self._cap = 1
        self._data = [None] * self._cap
        self._size = 0

    def __len__(self):
        return self._size

    def __getitem__(self, i):
        if not 0 <= i < self._size:
            raise IndexError("索引超出範圍")
        return self._data[i]

    def _resize(self, new_cap):
        old = self._data
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[i]
        self._cap = new_cap

    def append(self, x):
        if self._size == self._cap:          # 容量滿 → 加倍
            self._resize(2 * self._cap)
        self._data[self._size] = x
        self._size += 1

    def insert(self, i, x):
        if not 0 <= i <= self._size:
            raise IndexError("插入位置不合法")
        if self._size == self._cap:
            self._resize(2 * self._cap)
        for j in range(self._size, i, -1):   # 由後往前右移
            self._data[j] = self._data[j - 1]
        self._data[i] = x
        self._size += 1

    def remove(self, i):
        if not 0 <= i < self._size:
            raise IndexError("刪除位置不合法")
        val = self._data[i]
        for j in range(i, self._size - 1):   # 左移覆蓋
            self._data[j] = self._data[j + 1]
        self._data[self._size - 1] = None
        self._size -= 1
        if 0 < self._size <= self._cap // 4: # 縮容避免浪費
            self._resize(self._cap // 2)
        return val

    def __repr__(self):
        return f"DynArray({self._data[:self._size]!r}, cap={self._cap})"

# 動手玩
a = DynArray()
for x in [3, 1, 4, 1, 5]:
    a.append(x)
print(a)            # 已擴容多次，容量為 2 的冪次
a.insert(2, 99)
print(a[2], len(a)) # 99 6
print(a.remove(0))  # 3

複雜度分析#

操作 時間 說明
索引存取 O(1) 起點 + i × 元素大小
append / pop 尾端 攤攤 O(1) 擴容偶發，總搬移 O(n)
insert / remove（中間） O(n) 需搬移至多 n 個元素
空間 O(n) 容量至多為長度的數倍

練習#

  1. 在 DynArray 加上 pop()（移除並回傳尾端元素），分析它是否也需要攤攤分析。
  2. 把擴容策略從「加倍」改成「每次擴 100 格」，插入 n=10000 個元素的總搬移次數會變成多少？兩種策略各適合什麼場景？
  3. 實作 shrink_to_fit()：把容量壓到正好等於長度，並說明為什麼不能在每次 remove 後都這樣做。