2.1 数组
前置：渐近界、递推式与摊还分析，约 35 分钟。本节把下标、长度、容量、移动量与摊还成本放进同一份动态数组合同。
数组的第一份合同
先分清 size 和 capacity：前者是当前元素数量，后者是现有存储空间能容纳的元素数量。它们看起来只差一个名词，混用以后却会制造不少 bug。
先把“数组”分成三层
抽象数组
抽象数组是一组带整数下标的槽位。只要下标有效，你就能直接读取或改写该槽位。
下标： 0 1 2 3 4
┌──────┬──────┬──────┬──────┬──────┐
值： │ 10 │ 20 │ 30 │ 40 │ 50 │
└──────┴──────┴──────┴──────┴──────┘固定长度数组
创建后长度不变。Java 的 int[]、C++ 的 std::array<int, N> 都属于这一类。你可以改元素，不能把长度从 5 改成 6；若要更多槽位，需创建另一个数组并复制。
Python 没有与 Java 原生数组完全相同的内置固定长度容器。tuple 长度不可变，但元素本身也不能替换；list 和 array.array 都能改变长度。因此把 array.array 称为静态数组并不准确；官方文档把它定义成受类型码约束的可变序列。
动态数组
动态数组维护两组数字：
size是当前保存的元素数。capacity是当前缓冲区能容纳的槽位数。
只要 size < capacity，末尾追加可以直接写下一个空槽。缓冲区满了，容器申请更大的连续槽位区，把旧元素搬过去，再写新元素。
size = 3, capacity = 5
┌──────┬──────┬──────┬──────┬──────┐
槽位： │ 10 │ 20 │ 30 │ 空闲 │ 空闲 │
└──────┴──────┴──────┴──────┴──────┘Python list、Java ArrayList 和 C++ std::vector 都属于动态数组家族，但它们的元素表示、增长策略和失效规则不同。
为什么索引访问是 Θ(1)
若每个槽位宽度固定，概念地址可以写成：
address(k) = base + k × slot_width在单位成本 RAM 模型中，这只需要固定数量的算术、边界检查和一次槽位访问，工作量不随数组长度 n 增长，所以是 Θ(1)。
这个公式是模型，不是“一定编译成一条乘法加一条加法”的机器指令保证。编译器、寻址模式、元素表示和运行时都会改变具体指令。
CPython 的 list 实现还多一层细节：连续槽位里存的是对象引用，整数或自定义对象本身可能位于别处。values[k] 仍能常数时间取到第 k 个引用，但不能据此声称所有对象内容连续排列。
可运行的动态数组模型
下面的 Python 3.10+ 类只实现本章需要的接口。它用翻倍策略演示几何增长，返回的移动次数只统计插删时的后缀移动，不含扩容复制和新槽位初始化。翻倍是这个教学模型的选择，不是 Python、Java 或 C++ 的固定增长合同。
读取和 pop 支持负下标；insert 则只接受 0 ≤ i ≤ size，不会像内置列表那样截断越界位置。operator.index 在修改前检查整数下标，避免无效插入先触发扩容。
# dynamic_array_demo.py
from operator import index as integer_index
class DynamicArray:
def __init__(self, initial_capacity: int = 2) -> None:
initial_capacity = integer_index(initial_capacity)
if initial_capacity <= 0:
raise ValueError("initial capacity must be positive")
self._buffer: list[object | None] = [None] * initial_capacity
self._size = 0
self.growths: list[tuple[int, int]] = []
@property
def size(self) -> int:
return self._size
@property
def capacity(self) -> int:
return len(self._buffer)
def _grow(self) -> None:
old_capacity = self.capacity
new_capacity = old_capacity * 2
new_buffer: list[object | None] = [None] * new_capacity
for index in range(self._size):
new_buffer[index] = self._buffer[index]
self._buffer = new_buffer
self.growths.append((old_capacity, new_capacity))
def _check_index(self, index: int) -> None:
if index < 0 or index >= self._size:
raise IndexError("index out of range")
def append(self, value: object) -> None:
if self._size == self.capacity:
self._grow()
self._buffer[self._size] = value
self._size += 1
def insert(self, index: int, value: object) -> int:
index = integer_index(index)
if index < 0 or index > self._size:
raise IndexError("insert index out of range")
if self._size == self.capacity:
self._grow()
movements = self._size - index
for position in range(self._size, index, -1):
self._buffer[position] = self._buffer[position - 1]
self._buffer[index] = value
self._size += 1
return movements
def pop(self, index: int = -1) -> tuple[object, int]:
index = integer_index(index)
if index < 0:
index += self._size
self._check_index(index)
value = self._buffer[index]
movements = self._size - index - 1
for position in range(index, self._size - 1):
self._buffer[position] = self._buffer[position + 1]
self._size -= 1
self._buffer[self._size] = None
return value, movements
def __getitem__(self, index: int) -> object:
index = integer_index(index)
if index < 0:
index += self._size
self._check_index(index)
return self._buffer[index]
def to_list(self) -> list[object]:
return [self._buffer[index] for index in range(self._size)]
def main() -> None:
values = DynamicArray(2)
for value in (10, 20, 30, 40):
values.append(value)
insert_movements = values.insert(1, 15)
removed, delete_movements = values.pop(2)
assert values.growths == [(2, 4), (4, 8)]
assert insert_movements == 3
assert (removed, delete_movements) == (20, 2)
assert values.to_list() == [10, 15, 30, 40]
assert values.capacity == 8
for old, new in values.growths:
print(f"扩容：{old} → {new}")
print(f"插入移动：{insert_movements}")
print(f"删除移动：{delete_movements}")
print(f"内容：{values.to_list()}")
print(f"容量：{values.capacity}")
print("数组检查通过")
if __name__ == "__main__":
main()运行：
python3 dynamic_array_demo.py输出：
扩容：2 → 4
扩容：4 → 8
插入移动：3
删除移动：2
内容：[10, 15, 30, 40]
容量：8
数组检查通过这段输出把四类成本分开了：
- 第三次和第五次写入遇到满缓冲区，触发复制。
- 在下标 1 插入时，先扩容复制 4 个旧槽位，再右移 3 个后缀元素；输出的 3 只记后一笔。
- 删除下标 2 时，后面的 2 个元素左移。
- 删除没有主动缩容，所以容量仍为 8。真实容器是否缩容由它自己的合同决定。
动态数组的操作成本
令插入或删除前的逻辑长度为 n。
| 操作 | 更精确的工作量 | 常见最坏紧界 | 说明 |
|---|---|---|---|
读取/改写有效下标 i | 常数 | Θ(1) | 不含元素自身操作成本 |
| 末尾追加，无扩容 | 常数 | Θ(1) | 写一个空槽 |
| 末尾追加，发生扩容 | 复制 n 个槽位 | Θ(n) | 单次最坏 |
| 连续追加 | 总复制量线性 | 摊还 Θ(1)/次 | 从空表、固定初始容量开始，以固定倍数增长 |
在下标 i 插入 | 移动 n - i 个槽位 | Θ(n) | 后缀移动之外，扩容还要复制旧槽位 |
删除下标 i | 移动 n - i - 1 个槽位 | Θ(n) | 删除末尾不移动后缀 |
| 无序按值查找 | 最多比较 n 次 | Θ(n) | 最好可首项命中 |
复制长度 k 的范围 | 复制 k 个槽位 | Θ(k) | 同时产生 Θ(k) 输出空间 |
不扩容时，在下标 i 插入一个元素需要 Θ(n - i + 1) 时间：移动后缀，再写入新值。加上的 1 保留了尾部插入的常数成本；一旦扩容，复制与初始化又把本次成本提高到 Θ(n)。
创建容量为 c 的本例数组，需要初始化 c 个槽位，时间与存储空间均为 Θ(c)。本例不缩容，删除后占用的空间由 capacity 决定，不能只按剩余 size 计算。growths 只是记录扩容的诊断列表。
追加为什么能摊还 Θ(1)
从空表和固定初始容量出发，假设每次以固定倍数（大于 1）扩容。用翻倍模型看，连续追加 n 个元素时，历史复制量小于：
1 + 2 + 4 + ... < 2n新缓冲区的初始化量同样构成几何级数，再加每个元素最初写入一次，总工作量是 Θ(n)。把它分摊到 n 次追加，每次为摊还 Θ(1)。
这不依赖随机性，也不表示每次追加的最坏成本都是常数。一次触发扩容的追加仍会复制已有元素。
不要把具体扩容倍数当作语言保证：
- CPython 可以调整
list的过度分配策略。 - Java
ArrayList只公开追加的摊还常数成本，不公开固定增长因子。 - C++ 标准要求
vector满足相应复杂度和连续性合同，不指定增长倍数。
搜索、排序与保持有序
无序数组按值查找最坏需要完整扫描，时间 Θ(n)。排序后可以二分查找，最坏时间 Θ(log n)，但有两个容易漏掉的成本：
- 对没有额外限制的不同元素，比较排序最坏需要
Ω(n log n)次比较；归并排序能达到Θ(n log n)。这不是每个输入都要做这么多比较。 - 若持续保持数组有序，在位置
i插入仍要移动后缀，最坏Θ(n)。
所以“二分查找快”不自动推出“有序数组适合频繁插入”。先看读取与更新的比例。
复制、切片与视图
Python 列表切片会创建浅拷贝：
original = [[1], [2], [3]]
copied = original[1:]
copied[0].append(99)
print(original) # [[1], [2, 99], [3]]切片复制了引用，没有递归复制所指对象。复制 k 个引用需要 Θ(k) 时间和新列表空间。
不同语言的范围 API 可能返回副本或视图。Java subList 是由原列表支持的视图；C++ 迭代器对描述范围本身不复制元素。使用这些 API 前要查清修改传播、生命周期与失效条件。
二维数据不一定是一块矩形内存
这段 Python 看似创建三行，实际只创建一个内层列表，再把同一引用放了三次：
wrong = [[0] * 3] * 3
wrong[0][0] = 7
print(wrong) # [[7, 0, 0], [7, 0, 0], [7, 0, 0]]用列表推导式创建独立行：
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 7
print(matrix) # [[7, 0, 0], [0, 0, 0], [0, 0, 0]]Python list-of-lists 和 Java arrays-of-arrays 都是嵌套引用结构，不能直接套用“整块矩阵按行连续”的结论。C、C++ 原生多维数组以及 NumPy 等数值库有各自明确的布局合同。分析行优先或列优先遍历前，先确认实际表示。
连续槽位与缓存局部性
数组的相邻槽位让处理器更容易利用空间局部性和预取。顺序扫描常常比追逐分散节点更适合缓存。这里说“常常”是有意的：
- 缓存行大小和层级因处理器而异。
- CPython
list连续的是对象引用，被引用对象仍可能分散。 - 元素尺寸、访问步长、分支、分配器和数据规模都会影响结果。
因此本章不提供“快多少倍”或固定内存延迟。复杂度用来判断增长，基准测试用代表真实负载的数据比较实现。缓存细节可继续阅读 Vol. 3：缓存与存储器层次。
三种语言里的对应物
| 需求 | Python | Java 17+ | C++ |
|---|---|---|---|
| 通用动态序列 | list | ArrayList<E> | std::vector<T> |
| 固定长度 | 约定不改长度；无完全对应内置类型 | T[] | std::array<T, N> |
| 紧凑同类数值 | array.array | 原生数值数组 | std::vector<T> / std::array<T, N> |
| 两端频繁进出 | collections.deque | ArrayDeque<E> | std::deque<T> |
这里的 std::vector<T> 连续元素模型要求 T 不是 bool；vector<bool> 可以压缩存位，不能当作连续的 bool 对象数组。
几个可查的合同：
- Python 官方教程说明
list.insert(0, value)和pop(0)会移动其他元素，并推荐队列使用collections.deque。array.array是可变的同类数值序列。 - Java
ArrayList公开常数时间索引与摊还常数追加。ensureCapacity可能减少渐进式重分配，但容量不是列表大小。 - C++
vector::reserve(n)保证在大小超过当前容量前不因后续插入而重分配。发生重分配时，元素引用、指针和迭代器都会失效；没有重分配时，插入点及其后的元素引用、指针和迭代器也会失效。标准草案的vector容量规则与修改器给出了这些条件。
这些容器默认都不因为“像数组”就自动获得线程安全。并发读写要遵循对应 API 的同步合同。
常见错误怎么定位
| 症状 | 先检查什么 |
|---|---|
IndexError / IndexOutOfBoundsException | 有效读取范围是 0 ≤ i < size |
| 插入后元素顺序错乱 | 是否从后向前右移，避免覆盖未搬元素 |
| 删除后末尾还留着引用 | 是否清空逻辑末尾槽位，避免无意保留对象 |
| 预留容量后读到了空值 | reserve/capacity 不会增加逻辑 size |
| 二维列表改一行却多行变化 | 是否用乘法重复了同一个行对象 |
| C++ 保存的指针突然无效 | 操作是否触发 vector 重分配或移动后缀 |
动手推导移动与扩容
- 给教学版
DynamicArray增加set(index, value)，并让越界规则与__getitem__一致。 - 推导在长度
n的数组下标i插入连续m个元素时，需要移动多少旧元素、写入多少新元素。 - 设计一个不自动缩容的理由，再设计一个需要缩容的负载；比较内存占用与复制次数。
- 分别用 Python list-of-lists 和一个明确连续布局的数值数组做行/列遍历基准。先写布局假设，再解释结果。
核对三笔成本
在长度 n 的动态数组下标 i 插入一个元素，需要移动 n-i 个旧元素；删除同一位置则移动 n-i-1 个。把教学实现的容量从 2 扩到 4、8，分别记录单次复制量，再用整段追加序列解释为什么摊还成本仍为 Θ(1)。
接着测试切片究竟返回副本还是视图，并构造一次二维列表行别名。索引访问快来自布局与成本模型，中间修改贵也来自维持同一套连续下标；两者不是互相矛盾的口诀。
继续学习：链表
链表靠链接维持顺序。下一节会说明，“改两条链接”只有在调用者已经握着正确节点或前驱时才是常数操作。