3.2　动态数组与扩容的摊还代价

学习目标：学完本节，你能

从零实现一个动态数组，理解 List<T> 的核心机制；
精确推导出"扩容搬运总量小于 $2n$"，从而证明摊还 $O(1)$；
说出"倍增"与"固定增量"的区别，并知道什么时候该预分配容量。

先修：3.1（数组的地址公式与操作代价）、1.4（摊还代价的概念）。 固定术语：动态数组、容量（Capacity）、摊还代价、预分配。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：定长数组的困境

C# 的 int[] 一旦创建，长度就固定了：

int[] a = new int[100];
a[100] = 5;      // 抛 IndexOutOfRangeException —— 装不下了

现在需求是"陆续加入 1000 个元素"。你有三个选择：

方案	做法	问题
① 一次申请足够大	`new int[1000000]`	浪费内存，而且经常猜不准 —— 猜小了要重来，猜大了白占
② 用链表	每个元素单独分配	失去随机访问和缓存友好性（第 4 章详解）
③ 动态数组	装满了就换块更大的地、整体搬家	偶尔要搬家，但摊还下来是 $O(1)$

List<T> 用的就是方案 ③。 1.4 节我们观察过它的扩容现象，本节我们要自己实现一遍，并且把这笔账算到底。

二、实现：MyList\

新建控制台项目，粘贴以下代码：

using System.Diagnostics;

// ============ 实验一：自己实现的动态数组，观察扩容过程 ============

Console.WriteLine("=== 实验一：MyList 的扩容过程 ===");

var myList = new MyList<int>();
Console.WriteLine($"初始容量: {myList.Capacity}");
Console.WriteLine();

int applied = 0;
int lastCapacity = myList.Capacity;

for (int i = 0; i < 1_000_000; i++)
{
    myList.Add(i);
    if (myList.Capacity != lastCapacity)
    {
        applied++;
        if (applied <= 8 || myList.Capacity >= 262_144)
            Console.WriteLine($"  第 {myList.Count,9:N0} 个元素时扩容: {lastCapacity,9:N0} -> {myList.Capacity,9:N0}");
        lastCapacity = myList.Capacity;
    }
}

Console.WriteLine();
Console.WriteLine($"总插入次数      : {myList.Count,12:N0}");
Console.WriteLine($"总扩容次数      : {myList.GrowCount,12:N0}");
Console.WriteLine($"总搬运元素次数  : {myList.TotalMoved,12:N0}");
Console.WriteLine($"平均每次插入搬运: {(double)myList.TotalMoved / myList.Count,12:F3} 次");
Console.WriteLine();
Console.WriteLine($"理论：等比数列 4+8+16+... 的和 < 2n = {2_000_000:N0}");
Console.WriteLine($"      实测搬运量 {myList.TotalMoved:N0}，确实小于 2n -> 摊还 O(1) 成立");
Console.WriteLine();

// ============ 实验二：正确性验证 ============

Console.WriteLine("=== 实验二：和官方 List<T> 逐项对比 ===");

var mine = new MyList<int>();
var official = new List<int>();
var rng = new Random(42);

for (int i = 0; i < 100_000; i++)
{
    int v = rng.Next(0, 1_000_000);
    mine.Add(v);
    official.Add(v);
}

bool sameCount = mine.Count == official.Count;
bool sameContent = true;
for (int i = 0; i < mine.Count; i++)
{
    if (mine[i] != official[i]) { sameContent = false; break; }
}

Console.WriteLine($"  元素个数一致: {sameCount}  ({mine.Count:N0} vs {official.Count:N0})");
Console.WriteLine($"  逐项内容一致: {sameContent}");
Console.WriteLine();

// ============ 实验三：预分配容量的收益 ============

Console.WriteLine("=== 实验三：预分配容量 vs 让它自己扩容 ===");

const int N = 10_000_000;
var sw = new Stopwatch();

// 预热
{
    var warm = new MyList<int>();
    for (int i = 0; i < 100_000; i++) warm.Add(i);
}

sw.Restart();
var auto = new MyList<int>();
for (int i = 0; i < N; i++) auto.Add(i);
sw.Stop();
double autoMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
var pre = new MyList<int>(N);                 // 提前告诉它要装多少
for (int i = 0; i < N; i++) pre.Add(i);
sw.Stop();
double preMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  不预分配（{N:N0} 个元素）: {autoMs,9:F2} ms   扩容 {auto.GrowCount,3} 次，搬运 {auto.TotalMoved,12:N0} 次");
Console.WriteLine($"  预分配  （容量 {N:N0}）: {preMs,9:F2} ms   扩容 {pre.GrowCount,3} 次，搬运 {pre.TotalMoved,12:N0} 次");
Console.WriteLine($"  预分配快 {autoMs / preMs:F2} 倍");
Console.WriteLine();

// 类声明必须放在顶级语句之后
public class MyList<T>
{
    private T[] _items;
    private int _count;

    public MyList(int capacity = 0)
    {
        _items = capacity > 0 ? new T[capacity] : Array.Empty<T>();
    }

    public int Count => _count;
    public int Capacity => _items.Length;

    /// <summary>扩容次数，仅用于本节的统计演示</summary>
    public int GrowCount { get; private set; }

    /// <summary>累计搬运的元素个数，仅用于本节的统计演示</summary>
    public long TotalMoved { get; private set; }

    public void Add(T item)
    {
        if (_count == _items.Length)          // 装满了，先扩容
            Grow();
        _items[_count] = item;
        _count++;
    }

    private void Grow()
    {
        int newCapacity = _items.Length == 0 ? 4 : _items.Length * 2;   // 倍增
        var newItems = new T[newCapacity];
        Array.Copy(_items, newItems, _count);                            // 把老元素搬过去
        TotalMoved += _count;
        GrowCount++;
        _items = newItems;
    }

    public T this[int index]
    {
        get
        {
            // 用 (uint) 转换可以一次性挡掉负数和越界两种情况
            if ((uint)index >= (uint)_count)
                throw new ArgumentOutOfRangeException(nameof(index));
            return _items[index];
        }
        set
        {
            if ((uint)index >= (uint)_count)
                throw new ArgumentOutOfRangeException(nameof(index));
            _items[index] = value;
        }
    }
}

代码里有三处值得注意的设计：

_count 与 _items.Length 是两回事。 _count 是"装了几个"，_items.Length（也就是 Capacity）是"能装几个"。前者一定小于等于后者。
Grow() 里的倍增：_items.Length * 2。这个 2 是整节的关键，第三节会说明为什么。
索引器里的 (uint)index >= (uint)_count：把 int 转成 uint 后，负数会变成极大的正数，所以一次比较就能同时挡掉"下标为负"和"下标越界"两种情况。

三、摊还分析：凭什么是 $O(1)$

先看实验一的实测输出：

=== 实验一：MyList 的扩容过程 ===
初始容量: 0

  第         1 个元素时扩容:         0 ->         4
  第         5 个元素时扩容:         4 ->         8
  第         9 个元素时扩容:         8 ->        16
  第        17 个元素时扩容:        16 ->        32
  第        33 个元素时扩容:        32 ->        64
  第        65 个元素时扩容:        64 ->       128
  第       129 个元素时扩容:       128 ->       256
  第       257 个元素时扩容:       256 ->       512
  第   131,073 个元素时扩容:   131,072 ->   262,144
  第   262,145 个元素时扩容:   262,144 ->   524,288
  第   524,289 个元素时扩容:   524,288 -> 1,048,576

总插入次数      :    1,000,000
总扩容次数      :           19
总搬运元素次数  :    1,048,572
平均每次插入搬运:        1.049 次

理论：等比数列 4+8+16+... 的和 < 2n = 2,000,000
      实测搬运量 1,048,572，确实小于 2n -> 摊还 O(1) 成立

注意两个数字：扩容只发生了 19 次，而插入有 100 万次。 也就是说，99.998% 的 Add 操作根本没扩容，就是往数组的下一个空位放一个值 —— 纯粹的 $O(1)$。

那么那 19 次扩容呢？把搬运总量算出来就知道了。

每次扩容搬运的元素个数，正好是"当时的元素个数"，也就是容量序列：

$$4 + 8 + 16 + 32 + \cdots + 262144 + 524288$$

这是一个等比数列（公比为 2）。等比数列有一个漂亮的性质：

等比数列的和，小于最后一项的 2 倍。

（因为 $a + 2a + 4a + \cdots + 2^k a = (2^{k+1} - 1)a < 2 \cdot 2^k a$。）

所以无论插入多少元素，搬运总量永远小于 $2n$：

$$\text{总搬运量} < 2n$$

把它摊还到 $n$ 次插入上：

$$\text{平均每次插入的搬运量} < \frac{2n}{n} = 2 = O(1)$$

这就是摊还 $O(1)$ 的完整证明。

实测完美吻合：100 万次插入，搬运 1,048,572 次，平均 1.049 次 —— 确实小于 2。

为什么实测是 1.049 而不是接近 2？ 因为 2 是最坏情况的上界。实际平均值取决于 $n$ 和"2 的幂"有多接近。如果 $n$ 恰好等于 2 的幂（比如 $n = 524{,}288$），平均值会接近 2；如果 $n$ 刚好比某个 2 的幂大一点点（比如 $n = 524{,}289$），平均值就接近 1。

但无论怎么波动，它永远小于 2。 这就是上界的意义。

实验三的数据可以验证这一点（插入 1000 万个元素）：

  不预分配（10,000,000 个元素）:     46.48 ms   扩容  23 次，搬运   16,777,212 次

$16{,}777{,}212 \div 10{,}000{,}000 = 1.68$ 次/插入 —— 也在 1 到 2 之间，同样小于 2。

四、为什么必须"倍增"

上一节证明了 $O(1)$，但这个证明完全依赖于"乘 2"这个选择。如果改成每次只增加固定数量，结论会彻底崩塌。

设每次扩容只增加 1000 个容量，那么插入 $n$ 个元素需要扩容约 $\frac{n}{1000}$ 次。总搬运量是：

$$1000 + 2000 + 3000 + \cdots + n = 1000 \cdot \left(1 + 2 + \cdots + \frac{n}{1000}\right) \approx \frac{n^2}{2000}$$

这是等差数列，求和得到 $n^2$ 级。 摊还到每次插入就变成了 $O(n)$ —— 比倍增策略差了整整一个量级。

等差 vs 等比，差的就是这个。

倍增（等比）：上次搬过的元素，要过很久才会再搬一次。总搬运量被"最后一项"主导，是 $O(n)$。

固定增量（等差）：随着元素变多，扩容越来越频繁。总搬运量是 $O(n^2)$。

这就是为什么 .NET、Java、C++ 的动态数组全都采用倍增策略。（1.4 节的练习 1.4.3 让读者自己推导过这个结论。）

五、预分配的收益

既然扩容要搬运元素，那"提前告诉它要装多少"就能完全避免这笔开销。实验三的实测：

=== 实验三：预分配容量 vs 让它自己扩容 ===
  不预分配（10,000,000 个元素）:     46.48 ms   扩容  23 次，搬运   16,777,212 次
  预分配  （容量 10,000,000）:     24.85 ms   扩容   0 次，搬运            0 次
  预分配快 1.87 倍

1.87 倍，代码改动只有一处：

var auto = new MyList<int>();          // 不预分配：扩容 23 次，搬运 1677 万次
var pre  = new MyList<int>(N);         // 预分配：    扩容  0 次，搬运      0 次

工程建议：当你能估算出元素数量时，总是预分配容量。
// 常见写法
var list = new List<Order>();
var result = new List<Order>(orders.Count);        // 已知上界，直接给容量
var dict = new Dictionary<string, int>(capacity: 1024);

// LINQ 里的 ToList() 不给你这个机会，但 ToArray/ToDictionary 有容量重载
这是 C# 里性价比最高的一条微优化：一行改动、零风险、接近 2 倍的收益。

但要注意两个前提：

得估得准。 如果估大了（比如估 100 万实际只有 1000 条），你白白占用了几 MB 内存。小数组上这点无所谓，大数组上要谨慎。
只在"确实要放很多元素"时才有意义。 放 10 个元素时，预分配省下的时间是纳秒级。

六、和官方 List\ 的关系

实验二的输出：

=== 实验二：和官方 List<T> 逐项对比 ===
  元素个数一致: True  (100,000 vs 100,000)
  逐项内容一致: True

我们实现的 MyList<T> 与 List<T> 逐项一致。 这不是巧合 —— List<T> 的核心就是这个思路。

官方的 List<T> 在此基础上还做了这些事：

官方实现多做的	为什么
更完整的参数校验	边界情况的错误信息更清晰
`RemoveAt` / `Insert` / `IndexOf` 等 API	我们只实现了最小可用的部分
自定义的 `Enumerator`（结构体）	避免 `foreach` 时产生装箱和堆分配
`EnsureCapacity` / `TrimExcess`	让使用者能手动控制容量
针对 `Array.Copy` 的各种优化	在某些情况下用更快的底层指令
`ICollection<T>` 等一堆接口	与其他库的互操作性

本节的目的不是让你以后自己写 List（那通常是个坏主意），而是让你知道：

当你写下 list.Add(x) 时，背后发生的事是"绝大多数时候 $O(1)$，偶尔 $O(n)$，平均下来 $O(1)$"。 这样你在评估性能、排查卡顿时，心里有底。

七、练习

练习 3.2.1（推演）如果 MyList 的初始容量不是 4 而是 1，扩容策略仍是倍增。插入 100 个元素，一共会扩容多少次？搬运总量是多少？

练习 3.2.2（估算）一个动态数组采用倍增策略，从容量 16 开始。要插入 1,000,000 个元素。 (a) 容量最终会扩到多少？ (b) 总共扩容多少次？ (c) 搬运总量大约是多少？

练习 3.2.3（判断）判断对错并说明理由： (a) 因为 Add 是摊还 $O(1)$，所以每次 Add 都很快。 (b) 预分配容量总是能提升性能，所以应该到处都用。 (c) 既然倍增策略这么好，那把倍率从 2 改成 10 会不会更好？

练习 3.2.4（工程判断）下面三个场景，哪些应该预分配容量？分别说明理由。 (a) 从数据库读取约 5 万条订单，放进 List<Order> (b) 一个缓存，最多存 100 个元素，用 List<string> (c) 一个方法要根据输入动态生成结果，输入规模不确定（可能 10 个，也可能 100 万个）

练习 3.2.5（挑战·面试题）有一个动态数组，采用倍增策略。现在要求实现一个 RemoveAll 操作：删除所有满足条件的元素。 (a) 如果边遍历边删除，用 RemoveAt(i) 逐个删，复杂度是多少？为什么？ (b) 给出一个 $O(n)$ 的方案（提示：想想 3.3 节的"同向双指针"）。

八、练习答案

3.2.1

从容量 1 开始倍增，容量序列是：$1, 2, 4, 8, 16, 32, 64, 128$。

要装下 100 个元素，最终容量需要到 128。

扩容次数：从 1 扩到 128，一共 $2^0 \to 2^1 \to \cdots \to 2^7$，即 7 次。

搬运总量：每次扩容搬运"当时的元素个数"：

$$1 + 2 + 4 + 8 + 16 + 32 + 64 = 127$$

（严格说，从容量 1 扩容到 2 时，搬运 1 个；扩到 4 时搬运 2 个……扩到 128 时搬运 64 个。）

总量 127，小于 $2 \times 100 = 200$ ✓ 仍然满足小于 $2n$ 的上界。

注意初始容量：容量为 1 时第一次 Add 就要扩容，比初始容量 4 多折腾几次。但总搬运量依然是 $O(n)$ 量级，上界 $2n$ 不变。初始容量只影响常数，不影响量级。

3.2.2

(a) 容量序列：$16, 32, 64, \ldots$，是 2 的幂。找最小的 $2^k \geq 1{,}000{,}000$：

$2^{19} = 524{,}288$（不够）；$2^{20} = 1{,}048{,}576$（够）。

所以最终容量是 1,048,576。

(b) 从 $2^4=16$ 到 $2^{20}$，一共 16 次扩容（指数从 4 到 20）。

(c) 搬运总量是各次容量的和：

$$16 + 32 + \cdots + 524{,}288 = 16 \cdot (2^{16} - 1) \approx 1{,}048{,}560$$

穷举验证思路：等比数列 $16, 32, \ldots, 524288$（共 16 项）的和 $= 16 \times (2^{16} - 1) = 16 \times 65535 = 1{,}048{,}560$。

接近但小于 $n = 1{,}000{,}000$ —— 平均每次插入搬运约 1.05 次。

注意这里体现的一个现象：当 $n$ 刚好大于某个 2 的幂时，平均搬运量接近 1；当 $n$ 刚好等于某个 2 的幂时，平均搬运量会接近 2。但永远小于 2。

3.2.3

(a) 错。 "摊还 $O(1)$"是平均概念，不保证每一次都快。那 19 次（或 23 次）扩容，每一次都是实打实的 $O(n)$。

这个区别在对延迟敏感的系统里非常重要：一个游戏服务器、一个高频交易系统，可能会因为某一次 Add 恰好触发扩容而产生明显的卡顿（这个现象叫"延迟毛刺"）。对策：如果确实不能接受毛刺，就在初始化时预分配足够的容量，把扩容彻底消除。
(b) 错。 预分配有两个前提：估得准、确实要放很多元素。估大了浪费内存（100 万容量的 List<int> 就是 4 MB），放 10 个元素时预分配毫无意义。

更危险的情况：在循环里对每个小列表都预分配一个大容量，会造成大量内存浪费。
(c) 需要分情况，一般来说不是。
- 好处：倍率越大，扩容次数越少，总搬运量越小。倍率为 $k$ 时，总搬运量约为 $\frac{n}{k-1}$。倍率 10 比倍率 2 的搬运量少约 9 倍。
- 坏处：平均浪费的内存更多。倍率为 2 时，数组平均有 50% 的空间浪费；倍率为 10 时，平均可能有 90% 的空间浪费。对于大数组，这是灾难性的。
- 结论：2 是内存与时间的平衡点。 主流实现（.NET、Java、C++ 的 vector）都用 1.5 或 2 倍，是经过长期实践验证的选择。

3.2.4

(a) 应该预分配。 已知规模（5 万），且确实要放很多元素。new List<Order>(50000) 一行改动，省掉十几次扩容搬运。
(b) 不需要。 $n$ 只有 100，$O(n)$ 的搬运是纳秒级，预分配省下的时间可以忽略。而且列表小、内存影响也小，但代码多了一处噪音没有收益。保持简单。
(c) 视情况，通常用估算值。
- 如果完全不确定，就不要预分配 —— 让倍增策略自己处理，它的摊还开销本来就很小。
- 如果有一个常见的规模（比如"通常 1000 条左右"），可以用一个保守的初始容量（如 64 或 256），既避免最前面几次频繁扩容，又不会浪费太多内存。
- 绝对不要按最坏情况（100 万）预分配，因为大多数调用只有 10 条 —— 那会浪费大量内存。
  
  判断原则：预分配的价值 = 省下的搬运开销 − 浪费的内存成本。规模已知且大时为正，规模未知或很小时接近零。

3.2.5

(a) $O(n^2)$。

原因：每次 RemoveAt(i) 都要把位置 $i$ 后面的所有元素往前挪一格，单次是 $O(n)$。如果数组里有 $m$ 个元素要被删除，就是 $O(m \cdot n)$，最坏情况（几乎所有元素都要删）是 $O(n^2)$。

更隐蔽的坑：如果边遍历边删，还会因为下标变化而漏掉元素：

// 错误示范
for (int i = 0; i < list.Count; i++)
{
    if (ShouldRemove(list[i]))
        list.RemoveAt(i);      // 删除后，原来 i+1 的元素移到了 i 位置
                               // 但循环的 i++ 让它被跳过了！
}

(b) $O(n)$ 的方案 —— 同向双指针（原地覆盖）：

// 思路：用慢指针记录「保留区」的末尾，快指针扫描全部元素
static int RemoveAll<T>(MyList<T> list, Func<T, bool> shouldRemove)
{
    int slow = 0;                              // 保留区的下一个空位
    for (int fast = 0; fast < list.Count; fast++)
    {
        if (!shouldRemove(list[fast]))
        {
            list[slow] = list[fast];           // 把要保留的搬到前面
            slow++;
        }
    }
    // 截断到 slow（真实实现需要能修改 _count）
    // list.Truncate(slow);
    return slow;                               // 返回新的元素个数
}

每个元素只被访问一次，只被写一次，所以是 $O(n)$。

这就是 3.3 节"同向双指针"的思想。它的关键在于：不要一个个搬，而是一次遍历、就地覆盖。

顺带一提，C# 的 List<T>.RemoveAll 正是这么实现的 —— 官方文档明确说明它是 $O(n)$，而不是 $O(n^2)$。你可以自己去看 List<T>.RemoveAll 的源码验证。

而这个方案能成立，靠的正是数组的"连续内存 + 可按下标读写" —— 3.1 节讲的随机访问 $O(1)$，在这里变成了一个实实在在的性能优势。

九、常见错误

误区	纠正
认为 `Add` 永远是 $O(1)$	摊还 $O(1)$ 是平均概念。撞上扩容的那一次是实打实的 $O(n)$。对延迟敏感的系统要预分配。
用固定增量扩容	会让摊还代价从 $O(1)$ 退化到 $O(n)$（总搬运量从 $O(n)$ 变成 $O(n^2)$）。必须用倍增。
预分配时按最坏情况估	估大了浪费内存。100 万容量的 `List<int>` 就是 4 MB，`List<Order>` 可能是几十 MB。
在循环里 `RemoveAt(i)`	每次 $O(n)$，循环下来是 $O(n^2)$。应该用 `RemoveAll`（$O(n)$）或者双指针就地覆盖。
边遍历边删还递增下标	删除后后面元素前移，`i++` 会跳过一个元素。这是很隐蔽的逻辑 bug，不是性能问题。
认为倍率越大越好	倍率大省时间但浪费内存。倍率 2 时平均浪费 50% 空间，已经是平衡点。

十、本节总结

动态数组 = 数组 + 倍增扩容。核心机制是：装满了就申请一块两倍大的新数组，把老元素整体搬过去。
扩容只发生在少数几次：100 万次插入只扩容 19 次，99.998% 的 Add 是纯 $O(1)$。
摊还 $O(1)$ 的证明：每次搬运量构成等比数列，其和小于最后一项的 2 倍，所以总搬运量 $< 2n$，摊还到每次插入是 $O(1)$。
必须用倍增，不能用固定增量：等差求和得到 $O(n^2)$，会让摊还代价退化成 $O(n)$。
预分配的收益实测为 1.87 倍，且只需改一行代码。当你能估算规模且规模较大时，总是预分配。
摊还 ≠ 每次都快：那 19 次扩容每次都是 $O(n)$。对延迟敏感的场景要留意这个"毛刺"。

下一节衔接：本节练习 3.2.5 里已经悄悄用上了一个技巧 —— 用两个下标（一快一慢）在一趟遍历里完成原地删除。这是双指针最简单的一种形态。下一节我们会系统地讲这个技巧，它能把你以前写的很多 $O(n^2)$ 暴力解法直接降到 $O(n)$。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "3.2",
  "title": "动态数组与扩容的摊还代价",
  "covered": [
    "从零实现 MyList<T>（Add / 倍增扩容 / 索引器 / 容量与计数分离）",
    "扩容 19 次、搬运 1048572 次的实测（100 万次插入）",
    "摊还 O(1) 的完整证明（等比数列和 < 2 倍最后一项）",
    "倍增 vs 固定增量的量级差异（O(n) vs O(n^2)）",
    "预分配容量的收益实测（1.87 倍）",
    "与官方 List<T> 的逐项一致性验证",
    "摊还≠每次都快（延迟毛刺）与 RemoveAll 双指针方案"
  ],
  "unresolved": [
    "RemoveAll 的双指针思想在 3.3 正式展开",
    "环形缓冲区留到 5.2",
    "LinkedList<T> 的取舍留到第 4 章"
  ],
  "canonical_terms": {
    "动态数组": "可自动扩容的数组，C# 中为 List<T>",
    "容量（Capacity）": "底层数组能装多少个元素，与 Count 不同",
    "预分配": "创建时指定容量，避免后续扩容搬运",
    "摊还代价": "一系列操作的总代价除以操作次数"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已在 1.4 见过 List<T> 的扩容现象，在 3.1 掌握数组的随机访问",
    "读者会使用泛型类的基本语法"
  ],
  "word_count_actual": 2260,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch03/Sec32/",
    "实测数据逐项核对：扩容19次/搬运1048572次/平均1.049次；预分配 46.48ms vs 24.85ms(1.87倍)",
    "与 List<T> 的正确性对比通过（10 万项逐项一致）",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "next": "3.3 双指针技巧"
}

3.2　动态数组与扩容的摊还代价