学习目标
完成本节后，你应该能够：
- 解释为什么同样写法的 O(1) 访问，实际代价可能相差数百倍；
- 用「操作次数 × 单次操作代价」区分大 O 能表达和不能表达的部分；
- 从缓存行和内存布局出发，说明数组遍历通常比链表遍历快的原因；
- 用访问模式解释快速排序在实践中通常快于归并排序。
从一句话开始
阅读提示
本节会反复使用 O(n)、O(log n) 这类记号。如果还没有时间复杂度基础，请先阅读 0.2 时间与空间复杂度概论，再回到本节。
数据结构是对内存的布局，算法是对数据的操作。
这句话不是比喻。数组在物理上就是一段连续的地址空间，链表在物理上就是一堆散落在堆上的节点，每个节点带一个指向下一个节点的指针。我们写的每一行关于数据结构的代码，最终都会落到内存的某个布局上；我们写的每一个算法，最终都是在以某种顺序访问这块布局。
理解了这一点，很多原本要死记的结论，就变成了可以从硬件直接推出来的东西。为什么数组按下标访问是常数时间？因为内存控制器天生就会做「基地址加偏移量」这个运算。为什么链表遍历比数组慢？不是大 O 的错，是缓存命中率的错。
存储器是分层的
在讲布局之前，得先把存储器本身理清。从 CPU 往外，依次是：
寄存器 → L1 cache → L2 cache → L3 cache → 主存(RAM) → 硬盘(SSD/HDD)
越往里越快，同时也越小、越贵。具体的延迟数字，Jeff Dean 整理过一组常被引用的数据 [1]：
| 访问目标 | 大约延迟 |
|---|---|
| 寄存器 | ~1 周期 |
| L1 缓存 | 0.5 ns |
| L2 缓存 | 7 ns |
| L3 缓存 | 12 ns |
| 主存（RAM） | 100 ns |
| SSD 随机读 | 150 μs |
| 机械硬盘寻道 | 10 ms |
从 L1 到主存，延迟差了约两百倍；从主存到机械硬盘，再差约十万倍。这不是可以忽略的常数，而是决定一个数据结构在某个场景下能不能用的分水岭。所以一个很自然的判断就是：尽量避免让程序频繁地跑到高层、耗时长的那几层去取数据，这是加快代码效率的一个很有效的手段。
缓存行：CPU 一次搬 64 字节
上面的分层图讲的是「数据离 CPU 有多远」，但还有一个独立的事实同样关键：CPU 访问内存时不是按字节取的，而是按缓存行取的，一个缓存行通常是 64 字节 [2]。
你只想读地址 0x1000 上的一个 int，内存控制器实际把 0x1000 开始的一整段 64 字节都搬进了缓存。下次你再访问 0x1004，它已经在缓存里了，几乎免费。
两个概念别混
「存储分层」回答的是数据在哪一层，决定了一次未命中的代价有多大；「缓存行」回答的是一次搬运多少，决定了连续访问能免费带走多少邻居。两者合起来，才拼出「内存视角」的完整画面。
缓存行直接带来一个结果：连续访问快，跳跃访问慢。下面要说的「单次操作代价」，根源就在这里。
O(n) 其实该叫「操作复杂度」
这里有一个在数据结构学习里很容易被忽略的漏洞。
我们平时说 O(n)、O(log n)，把它叫「时间复杂度」。但仔细想想，大 O 表示的到底是什么？它表示的是代码运行的次数——也就是基本操作的执行次数。访问了 n 次元素，就是 O(n)；对半砍了 log n 次，就是 O(log n)。
这里要先说清楚：「时间复杂度」这个叫法本身并没有错，它建立在经典的 RAM 模型之上——在这个模型里，我们假设每一次基本操作（一次加法、一次比较、一次内存访问）的代价都相同。既然每次操作的代价一样，「执行了多少次」自然就等于「花了多少时间」，所以把「次数」叫「时间」是成立的。
问题在于，真实硬件破坏了 RAM 模型的这个假设。一次访问和一次访问的代价，在物理上可以差几百倍。一旦这个前提不成立，「操作次数」和「真实耗时」就不再等价了。
所以更准确的叫法，或许是「操作复杂度」——它描述的始终只是操作的次数；而真实的耗时，还得再乘上每次操作的代价。这中间差出来的那一环，就是基本操作本身的时间。
我们往往会自动脑补：基本操作嘛，那不就是 O(1) 的操作吗？访问一个 arr[i]、调用一个 printf，难道不是 O(1) 级别的吗？当然是。但问题恰恰在这里——不站在内存的视角看，我们完全无法区别「数组遍历里那次访问的 O(1)」和「链表遍历里那次访问的 O(1)」，其实它们天差地别。
直接拿 L1 缓存举例：访问数组时，元素几乎都在 L1 缓存上，命中一次大概只要 4 个 CPU 周期；而链表遍历时，节点散落在内存里，很大概率触发缓存未命中，CPU 就要停滞几百个周期去等主存。所以同样是一个 O(1) 的访问，命中与未命中之间，能差出几百甚至上千倍。
核心洞见
大 O 记不住、而被「时间复杂度」这个名字糊弄过去的那一环，是单次操作的代价。
真实耗时 ≈ 操作次数（大 O） × 单次操作代价。
大 O 管住了左边那一项，右边那一项它看不见。而内存布局，恰恰决定的就是右边那一项。
数组和链表：同一个 O(n)，不同的现实
最直观的对比就是遍历。一个含 n 个 int 的数组和一个含 n 个 int 的链表，遍历的复杂度都是 O(n)。但实际耗时可以差好几倍，有时差一个数量级。
原因就在缓存行。数组的元素连续，遍历时每 64 字节的搬运能覆盖 16 个 int（假设 int 是 4 字节），后面 15 次访问直接命中缓存。链表的节点是逐个 new 出来的，物理上随机分布，每个节点访问一次缓存行，而且 CPU 的硬件预取器猜不出下一个节点在哪——因为下一个地址藏在当前节点的 next 指针里。
Bjarne Stroustrup 在他关于「应该避免链表」的演讲里给过一个直观的结果：遍历一个随机插入的 std::list 比遍历一个 std::vector 慢，哪怕链表在理论上占优的「中间插入」操作，在数据量能装进缓存的情况下也未必赢过数组 [3]。链表「O(1) 插入」的理论优势，被糟糕的缓存局部性抵消了。
这不是说链表没用，而是说：复杂度告诉你的是操作次数，内存布局告诉你的是每次操作的代价。两者都得看。
快排和归并：同为 O(n log n)，快排却更快
再拿排序举一个例子。快排和归并都是 O(n log n) 的算法，但实际使用中快排几乎总是更快。比如 LeetCode 912「排序数组」，把快排和归并分别提交就能发现，归并一般都弱于快排——每次提交会有差异，但整体规律是这样。
原因还是 cache 友好。快排是顺序访问加原地交换，全程几乎和数组遍历一样，缓存命中率很高。而归并排序同时遍历两个子数组，导致两个数据流随机交替访问，最后甚至还要把结果再复制一遍，缓存表现差得多。所以归并的常数因子，就被这个访问模式拖累了 [4]。
两个算法操作次数同量级，差的正是「单次操作的代价」这一项。
这个视角还能解释什么
把「数据结构是内存的布局」这个判断继续用下去，一批经典的设计决策就都有了统一的解释。不过在看答案之前，先自己推一步——这四个问题，答案都藏在前面两节里。
栈为什么通常用数组，不用链表？
先想：栈的进和出都发生在同一端，那么这一端对应数组的哪个位置？数组尾部的增删本来就只需要改一个下标，是 O(1)；而链栈每次入栈都要 new 一个节点，分配本身有开销，节点还散落在各处。
所以答案不是「栈规定用数组」，而是：栈的约束（只在一端操作）恰好让数组的最强项——尾部操作、连续访问——完整发挥出来，同时避开了数组的弱点（中间插入搬移）。约束和结构一旦对上，就是最优解。
堆为什么用数组存，不用指针？
先想：一棵树如果每个节点都存左右指针，那一百万个节点就要多存两百万个指针。有没有可能不存指针？
关键在堆要求是完全二叉树。把完全二叉树的节点按层从上到下、从左到右编号，父子关系就变成了纯粹的算术：位置 i 的节点，孩子正好是 2i 和 2i+1。既然下标能算出来，指针就是多余的。
于是堆这棵「逻辑上的树」，在物理上就是一段连续数组——既省下全部指针空间，又享受连续内存的缓存友好。堆是「逻辑结构是树、物理存储是数组」最干净的例子，也最能说明：逻辑结构不等于物理布局，聪明的物理布局能同时省空间又省时间。
哈希表为什么能 O(1) 查找？
先想：要快速定位一个元素，最直接的办法是什么？是「直接算出它的位置」——而这正是数组最擅长的事。
哈希表的做法就是：用哈希函数把键映射成一个下标，直接跳过去（这一步是数组的 O(1) 随机访问）；多个键撞到同一个下标时，再用链表兜底（这一步处理冲突）。拆开看，哈希表没有引入任何新东西，就是数组负责定位、链表负责冲突的组合。
数据库索引为什么用 B+ 树，不用红黑树？
先想：如果数据放在磁盘上，每一次访问都极其昂贵，这时你最想减少的是「访问次数」还是「访问的局部性」？
答案是访问次数。B+ 树一个节点存多个键，节点大小设计成对齐磁盘页（常见 4KB 或 16KB），一次 I/O 读一页就能带出大量有效键，树的高度被压到 3 到 4 层，查一条记录只要 3 到 4 次 I/O。红黑树每个节点只存一个键，一次比较一次 I/O，查一条记录要几十次 I/O [5]。
这正好呼应了开头那张分层图：场景从内存换成磁盘，最优解就跟着变——数据结构的优劣，取决于它跑在哪一层存储上。
交互式演示
下面这个演示把上面的结论变成了可以动手跑的实验：每个实验都提供真实计时（浏览器内运行）和小样本过程可视化，你可以自动播放或逐步前进，观察数组与链表、快排与归并、行优先与列优先、二分与线性查找在访问模式上的差异。
结论：避免缓存未命中
从内存的角度看代码，内存布局影响运行时的缓存命中率，进而影响代码的效率。所以万变不离其宗，落到最后就是一句话——尽量避免缓存未命中。
判断一个数据结构，不能只看复杂度，还要看它把数据放在了哪一层存储上、以什么顺序访问。两个同为 O(n) 的算法，一个连续访问、一个随机访问，前者可能快一个数量级；两个同为 O(log n) 的结构，一个在内存里、一个在磁盘上，实际体验天差地别。
这层道理一旦建立，就会贯穿后面所有章节。每学一个新结构，先问它的数据在内存里怎么放，再问它对缓存意味着什么，最后才问它的复杂度是多少。顺序不能反。
参考资料
- [1] Jeff Dean. Latency Numbers Every Programmer Should Know. https://gist.github.com/jboner/2841832
- [2] Ulrich Drepper. What Every Programmer Should Know About Memory. 2007. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
- [3] Bjarne Stroustrup. Why you should avoid Linked Lists. GoingNative 2012. https://www.youtube.com/watch?v=YQs6IC-vgmo
- [4] Robert Sedgewick, Kevin Wayne. Algorithms. 4th ed. Addison-Wesley, 2011. 第 2 章排序。
- [5] Abraham Silberschatz, Henry F. Korth, S. Sudarshan. Database System Concepts. 7th ed. McGraw-Hill, 2019. 第 14 章索引部分。