课程 · #1 / 11

数组

连续内存——一个 CPU 周期内完成按下标访问

init

at index 3 value

动手试试：点 read 让某个下标闪一下（绿色 = O(1)）。然后在靠前的下标处 insert，看右侧的格子像涟漪一样依次橙色右移——这就是被可视化出来的 O(n) 代价。

为什么它重要

数组是计算领域中最基础的数据结构。其余每一种数据结构，要么建立在数组之上，要么是为了弥补数组的局限而设计出来的。理解数组，就是理解计算机究竟如何存储和访问数据。

核心思想

想象走廊里有一排带编号的储物柜。每个柜子上都漆着一个号码（下标），你可以立刻走到 47 号柜子，因为你确切知道它在哪儿——你不需要先把 1 到 46 号挨个查一遍。

这就是数组。 它是一整块连续的内存，其中每个槽位都有一个固定的位置。

神奇之处：因为元素彼此紧挨着存放，按下标访问任意元素都是瞬时的——O(1)。计算机算的是：base_address + (index × element_size)。

局限之处：如果你想在中间插入一个新元素，它后面的所有元素都得整体后移——O(n)。就像往一个塞得满满当当的书架里插一本书。

要点回顾

按下标访问是 O(1) —— 这是数组最具决定性的优势
在任意位置插入/删除是 O(n)，因为要搬移元素
内存是连续的 —— 对缓存性能极其友好
大小通常是固定的；动态数组会把扩容的代价摊还掉

再深入一些

当你需要随机访问、又很少在中间插入/删除时，数组最能大放异彩。动态数组（Vec、ArrayList）通过在装满时将容量翻倍来处理扩容——这使得追加的摊还代价仍然是 O(1)。数组对缓存也很友好：顺序访问相邻元素很快，因为它们会被一起加载进 CPU 缓存。

为什么是"摊还" O(1) —— 翻倍扩容的证明

动态数组一开始有一个较小的容量（比如 4），每次装满就把容量翻倍。大多数 push 调用只是往一个空槽里写入——O(1)。但每隔一段就会发生一次：你把数组装满了，于是不得不分配一个两倍大的新数组，再把 n 个元素全部拷贝过去——这是 O(n)。

那么 push 真的是 O(1) 吗？在大量 push 上平均来看，是的。把从 1 个元素增长到 n 个元素所做的全部工作累加起来：

copies: 1 + 2 + 4 + 8 + … + n/2 + n
     = 2n − 1
     = O(n) total work spread across n inserts
     = O(1) per insert, amortized

这个几何级数每一项都翻倍，但前面那些项会缩小到一半。总工作量在 n 上仍是线性的。如果你不翻倍而是只加一半容量，那每次扩容都是 O(n)，你就拿不到摊还带来的红利——总工作量会攀升到 O(n²)。翻倍正是那个让账算得平的神奇常数。

这是摊还分析最经典的第一口尝鲜——同样的套路还会出现在哈希表的再散列、堆的建堆以及环形缓冲队列中。

缓存局部性 —— 那个数量级层面的原因

数组之所以快，不仅仅是因为 O(1) 访问——更是因为现代 CPU 会预取连续内存。当你读 arr[i] 时，CPU 会把一整条缓存行（通常 64 字节——16 个 int，或 8 个 double）加载进 L1 缓存。接着读 arr[i+1]、arr[i+2] 就都是免费的缓存命中了。

如果是一个数据散落在内存各处的链表，那么大多数指针解引用都会付出一次 L1 缺失的代价。这些常数是：

L1 命中：~1 ns（≈ 4 个 CPU 周期）
L2 命中：~3 ns
L3 命中：~10 ns
主存：~100 ns

在一个热点循环里，即便两者遍历都是 O(n)，数组也可能比装着相同元素的链表快 10–100 倍。大O把这件事藏起来了。机器人领域的经验法则是：对任何内层循环，优先用结构体数组（AoS）或数组结构体（SoA）；只在那种罕见的、需要凭一个活动节点引用做 O(1) 拼接的场景里，才保留链表。

数学细节

时间复杂度: Access: O(1); Search (unsorted): O(n); Insert at end: O(1) amortized; Insert at index i: O(n-i)
地址计算: address[i] = base + i × sizeof(element)

实现

Rust 中的数组

// Fixed-size array
let arr: [i32; 5] = [1, 2, 3, 4, 5];
let third = arr[2]; // O(1) access

// Dynamic array (Vec)
let mut vec = Vec::new();
vec.push(1); // O(1) amortized
vec.insert(0, 0); // O(n) - shifts all elements

关键操作

arr[i] - O(1) 随机访问
vec.push(x) - O(1) 摊还追加
vec.insert(i, x) - O(n) 插入
vec.remove(i) - O(n) 删除

练习

三道建立在数组之上的经典题目，每道演示一种不同的技巧：

两数之和 —— 简单 · 借助哈希表以空间换时间
最大子数组（Kadane 算法） —— 中等 · 单趟扫描维护运行状态
接雨水 —— 困难 · 双指针扫描并维护两侧最大值

→ 浏览全部练习题

🧱 数组