第 3 章　数组与字符串

本章解决的问题：为什么数组"按下标访问是 $O(1)$"？为什么在开头插入一个元素会这么慢？以及如何用双指针和滑动窗口，把大量 $O(n^2)$ 的暴力解法降到 $O(n)$。

3.1　连续内存：数组的红利与代价

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

  • 用地址公式解释数组随机访问为什么是 $O(1)$；
  • 说清中间插入/删除为什么是 $O(n)$，并估算代价；
  • 解释 CPU 缓存给数组带来的、大 O 记法看不见的额外优势。

先修：1.2（大 O 记法）、1.4（空间复杂度）。 固定术语：数组、随机访问、缓存行。 环境与版本：.NET 8 / C# 12（实验一需要 AllowUnsafeBlocks）。 预计阅读：25 分钟。

一、直觉：连号储物柜 vs 分散储物柜

数组像一排连号的储物柜：

  • 你站在第 1 号柜前，知道每个柜子宽 50 厘米；
  • 想问"第 7 号柜在哪"，不需要一个个走过去看 —— 直接算出它在 第 1 号柜右边 300 厘米。
  • 知道起点和间距，就能瞬间定位任意一个。

链表（第 4 章）像分散在整栋楼里的储物柜：

  • 每个柜子里放着一张纸条，写着"下一个柜子在 302 室"；
  • 想找第 7 个，必须从第 1 个开始，一个接一个地跑过去。

"连号"这两个字，就是数组全部优点和缺点的来源。

二、形式化：地址公式

数组（Array）：一块连续的内存区域，存放同类型的元素。

因为元素类型相同，所以每个元素占的字节数一样。设首地址是 $base$，每个元素占 $s$ 字节，那么第 $i$ 个元素的地址是：

$$\text{addr}(i) = base + i \times s$$

这个公式解释了随机访问：

访问 a[i] 时，CPU 只需要做一次乘法加一次加法，就能算出数据在哪，然后直接去取。不管 i 是 0 还是 1,000,000，耗时都一样。

随机访问（Random Access）：访问任意位置所需的时间与位置无关。这就是"$O(1)$ 按下标访问"的真正含义。

代价也随之而来。 因为内存必须连续，所以：

操作 为什么要挪动 代价
在中间或开头插入 要在 a[i] 处腾出一个位置，a[i] 及其后面所有元素都得往后挪一格 $O(n)$
在中间或开头删除 删掉后留下一个空洞，后面所有元素都得往前补一格 $O(n)$
尾部追加 如果后面还有空位，直接放就行 摊还 $O(1)$（3.2 节）
超出容量时扩容 找不到更大的连续空间，只能另找一块地、整体搬家 摊还 $O(1)$（3.2 节）

三、实验一：亲眼看到内存里的连续性

"连续"这两个字平时看不见。用 C# 的 unsafe 代码，我们可以直接读出每个元素的内存地址。

新建控制台项目，在 .csproj 里加上 <AllowUnsafeBlocks>true</AllowUnsafeBlocks>，然后粘贴：

using System.Diagnostics;

// ============ 实验一：数组元素在内存中是连续的 ============
// 用不安全代码直接读内存地址，亲眼确认「连续」这两个字。

unsafe
{
    int[] a = { 10, 20, 30, 40, 50 };

    Console.WriteLine("=== 实验一：数组元素的地址是连续的 ===");
    Console.WriteLine("（用 unsafe 代码直接读内存地址）");
    Console.WriteLine();

    fixed (int* p = a)
    {
        for (int i = 0; i < a.Length; i++)
        {
            long offset = (long)(p + i) - (long)p;
            Console.WriteLine($"  a[{i}] = {a[i],3}   相对首地址偏移 = {offset,3} 字节");
        }
    }

    Console.WriteLine();
    Console.WriteLine($"  每个 int 占 {sizeof(int)} 字节，所以 a[i] 的地址 = 首地址 + i * 4");
    Console.WriteLine($"  知道首地址和下标，一次乘加就能算出位置 -> 这就是随机访问是 O(1) 的原因");
}
Console.WriteLine();

实测输出：

=== 实验一：数组元素的地址是连续的 ===
（用 unsafe 代码直接读内存地址）

  a[0] =  10   相对首地址偏移 =   0 字节
  a[1] =  20   相对首地址偏移 =   4 字节
  a[2] =  30   相对首地址偏移 =   8 字节
  a[3] =  40   相对首地址偏移 =  12 字节
  a[4] =  50   相对首地址偏移 =  16 字节

  每个 int 占 4 字节，所以 a[i] 的地址 = 首地址 + i * 4
  知道首地址和下标，一次乘加就能算出位置 -> 这就是随机访问是 O(1) 的原因

偏移量是 0、4、8、12、16 —— 严丝合缝，一个字节都不差。 这就是"连续内存"。

（unsafe 和 fixed 的语法细节本书不展开，你只需要看懂输出。日常开发中不需要写这类代码，这里纯粹是为了"看见"。）

四、实验二：中间插入的代价

在同一个项目里，把下面代码加到后面：

// ============ 实验二：尾部追加 vs 头部插入 ============

var sw = Stopwatch.StartNew();

// 预热：先让 JIT 编译好，否则第一轮测量会把编译时间也算进去
{
    var warm = new List<int>();
    for (int i = 0; i < 50_000; i++) warm.Add(i);
    warm.Clear();
    for (int i = 0; i < 50_000; i++) warm.Insert(0, i);
}

Console.WriteLine("=== 实验二：尾部追加 vs 头部插入 ===");
Console.WriteLine($"{"操作次数",12} | {"尾部追加",12} | {"头部插入",12} | {"头部相对上次",14}");
Console.WriteLine(new string('-', 62));

double prevHeadMs = 0;

foreach (int n in new[] { 50_000, 200_000 })
{
    sw.Restart();
    var tail = new List<int>();
    for (int i = 0; i < n; i++) tail.Add(i);           // 追加到末尾，不用挪动任何元素
    sw.Stop();
    double tailMs = sw.Elapsed.TotalMilliseconds;

    sw.Restart();
    var head = new List<int>();
    for (int i = 0; i < n; i++) head.Insert(0, i);     // 每次都插到最前面，后面全部挪一格
    sw.Stop();
    double headMs = sw.Elapsed.TotalMilliseconds;

    string growth = prevHeadMs > 0 ? $"{headMs / prevHeadMs:F1} 倍" : "—";
    Console.WriteLine($"{n,12:N0} | {tailMs,9:F2} ms | {headMs,9:F2} ms | {growth,14}");
    prevHeadMs = headMs;
}

Console.WriteLine();
Console.WriteLine("  数据量涨了 4 倍，两种操作的耗时变化完全不同：");
Console.WriteLine("    尾部追加：几乎不变（线性，且常数极小）");
Console.WriteLine("    头部插入：涨了 16 倍（4^2 = 16，这正是 O(n^2) 的样子）");
Console.WriteLine();

实测输出（.NET 8 Release）：

=== 实验二：尾部追加 vs 头部插入 ===
        操作次数 |         尾部追加 |         头部插入 |         头部相对上次
--------------------------------------------------------------
      50,000 |      0.11 ms |     47.15 ms |              —
     200,000 |      0.33 ms |    748.79 ms |         15.9 倍

  数据量涨了 4 倍，两种操作的耗时变化完全不同：
    尾部追加：几乎不变（线性，且常数极小）
    头部插入：涨了 16 倍（4^2 = 16，这正是 O(n^2) 的样子）

这张表要这样读：

50,000 次 200,000 次 数据涨 4 倍，耗时涨
尾部追加 0.11 ms 0.33 ms 约 3 倍（线性）
头部插入 47.15 ms 748.79 ms 15.9 倍（平方）

为什么头部插入是 $O(n^2)$？ 因为每一次插入都是 $O(n)$：

  • 第 1 次插入：挪 0 个
  • 第 2 次插入：挪 1 个
  • 第 $n$ 次插入：挪 $n-1$ 个

总挪动量 $= 0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$ —— 平方级。

注意一个容易被误读的地方：单次 Insert(0, x) 的复杂度是 $O(n)$，不是 $O(1)$。如果你在循环里反复 Insert(0, ...)，整体就是 $O(n^2)$。

工程上的替代方案：如果你确实需要频繁在头部插入，考虑改用 LinkedList<T>（第 4 章）或者干脆倒着存、最后反转。

五、实验三：大 O 看不见的优势 —— CPU 缓存

现在看一个用大 O 记法完全分析不出来的性能差异。把下面代码加到最后：

// ============ 实验三：顺序访问 vs 随机访问（CPU 缓存效应） ============

const int M = 10_000_000;
int[] data = new int[M];
for (int i = 0; i < M; i++) data[i] = i;

// ---- 顺序访问 ----
sw.Restart();
long sumSeq = 0;
for (int i = 0; i < M; i++) sumSeq += data[i];
sw.Stop();
double seqMs = sw.Elapsed.TotalMilliseconds;

// ---- 随机访问 ----
// 关键：先把下标数组洗牌，这样两个循环的结构完全一样，
// 唯一的差别就是「内存访问模式」。否则随机数生成的开销会污染结果。
int[] indices = new int[M];
for (int i = 0; i < M; i++) indices[i] = i;

var rng = new Random(42);
for (int i = M - 1; i > 0; i--)                    // Fisher-Yates 洗牌
{
    int j = rng.Next(i + 1);
    (indices[i], indices[j]) = (indices[j], indices[i]);
}

sw.Restart();
long sumRand = 0;
for (int i = 0; i < M; i++) sumRand += data[indices[i]];
sw.Stop();
double randMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine("=== 实验三：顺序访问 vs 随机访问 ===");
Console.WriteLine($"  两者都是 {M:N0} 次加法，循环结构完全相同，只有内存访问顺序不同：");
Console.WriteLine();
Console.WriteLine($"  顺序访问: {seqMs,10:F2} ms   和 = {sumSeq:N0}");
Console.WriteLine($"  随机访问: {randMs,10:F2} ms   和 = {sumRand:N0}");
Console.WriteLine($"  随机访问慢 {randMs / seqMs:F1} 倍 —— 差别全部来自 CPU 缓存");
Console.WriteLine();
Console.WriteLine("  原因：CPU 读内存不是读 1 个字节，而是整条「缓存行」（通常 64 字节）一起读。");
Console.WriteLine("        顺序访问时，读到 a[0] 意味着 a[1]~a[15] 也已经在缓存里了，后面 15 次几乎免费；");
Console.WriteLine("        随机访问时，每次都要去主内存取一整条缓存行，却只用其中 4 个字节。");
Console.WriteLine();
Console.WriteLine("  这就是数组相对链表的最大隐藏优势：链表节点在内存里是散落的，无法利用缓存行。");

实测输出：

=== 实验三：顺序访问 vs 随机访问 ===
  两者都是 10,000,000 次加法，循环结构完全相同，只有内存访问顺序不同：

  顺序访问:       1.95 ms   和 = 49,999,995,000,000
  随机访问:      29.67 ms   和 = 49,999,995,000,000
  随机访问慢 15.3 倍 —— 差别全部来自 CPU 缓存

两个循环做的事情一模一样：都是 1000 万次加法。 唯一的区别是访问内存的顺序。结果差了 15 倍。

原因：CPU 不是按字节读内存的，而是按"缓存行"（Cache Line，通常 64 字节）整条读的。

  • 顺序访问：读到 data[0] 时，data[1] 到 data[15]（共 64 字节）已经一起被装进缓存了。接下来 15 次访问几乎不花时间 —— 直接从缓存拿。
  • 随机访问：每次跳到一个新位置，缓存里没有，必须去主内存搬一整条缓存行回来 —— 却只用其中 4 个字节。剩下 60 字节白白浪费。

这是大 O 记法完全分析不出来的东西。 两个循环都是 $O(n)$、都是 $n$ 次加法，大 O 说它们"一样快"。但在真实硬件上差了 15 倍。

1.2 节说过"复杂度描述趋势，不描述精确倍数"，这里是那条结论最有冲击力的例证。

这条结论在第 4 章会立刻派上用场：遍历链表时，每个节点在内存里是散落的，CPU 无法预取 —— 所以即使链表遍历和数组遍历都是 $O(n)$，数组版本也会快好几倍。

六、数组的完整操作代价表

把本节和 3.2 节的结论汇总（$n$ = 元素个数）：

操作 代价 原因
按下标访问 a[i] $O(1)$ 地址公式，一次乘加
修改 a[i] = x $O(1)$ 同上
尾部追加 Add 摊还 $O(1)$ 有空位直接放；偶尔扩容
头部/中间插入 Insert(i, x) $O(n)$ 后面所有元素要后移
头部/中间删除 RemoveAt(i) $O(n)$ 后面所有元素要前移
按值查找（无序） $O(n)$ 只能一个个看
按值查找（有序） $O(\log n)$ 二分查找（8.5 节之前会用到）
遍历 $O(n)$ 每个元素都要看，但缓存极友好

记住这张表，它是后面所有数据结构对比的基准。 每学一个新结构（链表、哈希表、树、堆），你都会回来和它比一遍。

七、练习

练习 3.1.1（算一算） 一个 int[] 的首地址是 0x1000（十六进制）。请问： (a) a[10] 的地址是多少？ (b) a[10] 和 a[11] 的地址相差多少字节？ (c) 如果换成 long[]（每个元素 8 字节），a[10] 的地址又是多少？

练习 3.1.2（估算代价） 一个订单列表有 10 万条数据。现在要在开头插入一条新订单。 (a) 大约要挪动多少个元素？ (b) 如果有 1000 个用户同时各插入一条，都在开头，总共挪动多少次？ (c) 你会怎么改进这个设计？

练习 3.1.3（判断） 下列说法是否正确？ (a) 数组的"随机访问是 $O(1)$"意味着读取 a[999999] 和读取 a[0] 耗时完全相同。 (b) 因为数组插入是 $O(n)$，所以数组是低效的数据结构。 (c) 两个都是 $O(n)$ 的算法，在真实机器上的耗时一定差不多。

练习 3.1.4（缓存推理） 在实验三的基础上回答： (a) 如果我把 data 数组的大小从 1000 万降到 1000（能完全放进 CPU 的一级缓存），顺序访问和随机访问的差距会变大还是变小？为什么？ (b) 遍历一个 int[] 和一个 LinkedList<int>（元素个数相同），哪个更快？为什么？

练习 3.1.5（挑战·工程） 你的系统需要维护一个"最近浏览商品"列表，最多保留 100 条，每次浏览新商品时加到最前面，超出 100 条就丢弃最旧的。 (a) 用 List<string> 实现，Insert(0, ...) 的代价是多少？在这个规模下可以接受吗？ (b) 如果需求变成"最多保留 100 万条"，你还会用同样的实现吗？给出你的方案。

八、练习答案

3.1.1

  • (a) addr(10) = 0x1000 + 10 × 4 = 0x1000 + 40 = 0x1028（40 的十六进制是 0x28）。
  • (b) 相差 4 字节，正好是一个 int 的大小。
  • (c) addr(10) = 0x1000 + 10 × 8 = 0x1000 + 80 = 0x1050（80 的十六进制是 0x50）。

要点：公式里的 $s$ 是元素类型的大小。int 是 4 字节，long 是 8 字节，所以同样下标 10，地址差了一倍。

3.1.2

  • (a) 大约 10 万个。插入到位置 0，意味着原有 10 万个元素全部要往后挪一格。
  • (b) $1000 \times 100{,}000 = 10^8$ —— 1 亿次元素移动。即使每次移动只要 1 纳秒，也要 0.1 秒，而且这还只是移动的耗时，不含其他开销。
  • (c) 几个方向：
    1. 改成尾部追加。如果业务允许，把"新的"放末尾、"旧的"放开头，插入就是 $O(1)$。查询时反向遍历即可。
    2. 改用 LinkedList<T>。头插是 $O(1)$（第 4 章），代价是失去随机访问和缓存友好性。
    3. 改用双端队列 LinkedList<T> 或环形缓冲区。如果需求本质是"先进先出"，环形缓冲区（5.2 节）是最优解。
    4. 批量处理。如果 1000 个插入可以攒起来，一次性重建数组反而更快（$O(n)$ 一次，而不是 $O(n)$ 一千次）。

3.1.3

  • (a) 基本正确，但有个重要前提。 地址计算和取数确实都是常数时间。但如果数组非常大，a[999999] 很可能不在 CPU 缓存里，需要去主内存取（约 100 纳秒）；而 a[0] 可能已经在缓存里（约 1 纳秒）。所以严格说：地址计算是 $O(1)$ 的，实际取数时间受缓存影响，相差可达上百倍。

    这正是大 O 记法的边界：它描述的是"随 $n$ 增长的趋势"，不描述常数。

  • (b) 错。 插入慢只是它的一个操作特征。数组的随机访问和缓存友好性在很多场景下是不可替代的。没有"低效的数据结构"，只有"用错场景的数据结构"。 事实上数组是使用最广泛的结构。
  • (c) 错。 实验三就是反例：两个 $O(n)$ 的循环差了 15 倍。大 O 相同不代表实际耗时相同，常数因子、缓存、分支预测都会影响。

3.1.4

  • (a) 差距会显著变小，可能完全消失。 原因是：当数组只有 1000 个 int（4 KB）时，整个数组都能放进一级缓存（通常 32 KB）。此时无论按什么顺序访问，数据都在缓存里，随机访问不再有"未命中"的惩罚。

    这条推论很有用：缓存效应只在数据量超过缓存容量时才明显。小数组上做微优化（比如特意改成顺序访问）是没有意义的。

  • (b) int[] 更快，而且差距通常有几倍。 原因有两层：

    1. 缓存行：数组元素连续，CPU 预取友好；链表节点散落在堆上，每跳一个节点都可能是一次缓存未命中。
    2. 额外内存访问：遍历链表时，访问一个节点的数据之前，必须先读它的 Next 指针——这本身也是一次内存访问。数组则是一次搞定。

    所以同样是 $O(n)$ 遍历，数组版本的实际耗时可能是链表的三分之一甚至更低。第 4 章会实测这个差距。

3.1.5

  • (a) Insert(0, ...) 的代价是 $O(n)$。但这里 $n$ 只有 100，完全可以接受 —— 挪动 100 个引用是纳秒级的事。

    这是本节最该记住的工程判断之一：$O(n)$ 不代表"慢"。$n$ 很小时，常数才是决定因素，而 List<T> 在这个规模下比任何"更聪明"的结构都快（因为它在缓存里，而且代码简单不易出错）。

  • (b) 100 万条时，$O(n)$ 的头插就不行了（每次要挪 100 万个引用）。方案：

    1. 环形缓冲区（推荐）。用一个固定长度 100 万的数组和两个指针（头、尾），插入就是"写一个位置 + 移动指针"，$O(1)$，而且不产生任何垃圾。这是 5.2 节的内容。
    2. LinkedList<T>。头插 $O(1)$，但每个节点都有额外的内存开销（对象头 + 两个指针，通常 24～32 字节），100 万条会占用几十 MB，且遍历慢。
    3. 分段数组。用多个小数组拼成一个逻辑上连续的序列，插入时只需要重排段内的少量元素。

    首选环形缓冲区：它的内存布局和数组一样连续（缓存友好），操作又是 $O(1)$，正好同时拿到了两个优点。

九、常见错误

误区 纠正
认为"数组插入是 $O(1)$" 尾部追加才是摊还 $O(1)$。头部/中间插入是 $O(n)$，因为要挪动后面的元素。
在循环里用 Insert(0, ...) 单次 $O(n)$，循环 $n$ 次就是 $O(n^2)$。实测 20 万次头部插入要 749 ms，而同样次数的尾部追加只要 0.33 ms。
以为大 O 相同就一样快 实验三里两个 $O(n)$ 的循环差了 15 倍。常数因子、缓存、分支预测都是真实存在的。
认为 $O(n)$ 一定很慢 $n$ 是 100 的时候，$O(n)$ 就是挪 100 个引用，纳秒级。先看 $n$ 的量级，再谈复杂度。
忽略缓存效应做微优化 数据量小于缓存容量时，缓存效应根本不存在。别在小数组上做无意义的"顺序访问优化"。

十、本节总结

  1. 数组是连续内存 + 同类型元素。地址公式 $\text{addr}(i) = base + i \times s$ 决定了随机访问是 $O(1)$。
  2. 连续性的代价：头部/中间插入或删除是 $O(n)$（要挪动元素）。实测 20 万次头部插入耗时 749 ms，是尾部追加的 2000 倍。
  3. 循环里 Insert(0, ...) 会退化成 $O(n^2)$ —— 这是很常见的性能陷阱。
  4. CPU 按缓存行（64 字节）读内存，所以顺序访问比随机访问快 15 倍。这是大 O 记法看不见的优势，也是数组相对链表最被低估的长处。
  5. $O(n)$ 不等于慢。 $n$ 小的时候，简单直白的数组实现往往是最优解。

下一节衔接：本节反复提到"扩容是摊还 $O(1)$"，但一直没算清这笔账。下一节我们从零实现一个动态数组，把扩容的搬运总量精确算出来，看看凭什么说它是 $O(1)$，以及"预分配容量"到底能快多少。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "3.1",
  "title": "连续内存：数组的红利与代价",
  "covered": [
    "连续内存的地址公式与 O(1) 随机访问的成因",
    "用 unsafe 代码实测数组元素的地址偏移（0/4/8/12/16）",
    "头部插入 vs 尾部追加的实测对比（O(n^2) vs 摊还 O(1)）",
    "CPU 缓存行导致的顺序/随机访问 15 倍差距",
    "数组完整操作代价表",
    "「大 O 相同不代表实际耗时相同」的实证"
  ],
  "unresolved": [
    "动态数组的扩容推导与预分配收益留到 3.2",
    "链表遍历的实测对比留到第 4 章",
    "二分查找留到后续章节",
    "环形缓冲区留到 5.2"
  ],
  "canonical_terms": {
    "数组": "连续内存中同类型元素的集合",
    "随机访问": "访问任意位置的时间与位置无关，即 O(1)",
    "缓存行": "CPU 从内存读取数据的最小单位，通常 64 字节"
  },
  "symbols_units": {
    "base": "数组首地址",
    "s": "每个元素占用的字节数",
    "addr(i)": "第 i 个元素的内存地址"
  },
  "assumptions": [
    "读者已掌握 1.2 的大 O 化简规则",
    "读者使用 x64 架构（缓存行 64 字节）"
  ],
  "word_count_actual": 1980,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch03/Sec31/（需 AllowUnsafeBlocks）",
    "实测数据逐项核对：头部插入 15.9 倍(理论16)、顺序/随机 15.3 倍",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版实验二只有 5 万一档且未预热，导致首轮 JIT 污染（200000 档反而更快）；已改为两档 + 显式预热重测"
  ],
  "next": "3.2 动态数组与扩容的摊还代价"
}

results matching ""

    No results matching ""