操作复杂度 ≠ 时间复杂度

数据结构是对内存的布局，算法是对数据的操作。大 O 记的其实是「操作次数」，我们却叫它「时间复杂度」——中间被忽略的那一环，是每一次操作的代价。

01存储器是分层的

越往里越快、越小、越贵。把鼠标移到每一层，看延迟差了几个数量级。
寄存器~1 周期
L1 缓存0.5 ns · ~64 KB
L2 缓存7 ns · ~512 KB
L3 缓存12 ns · 4–32 MB
主存（RAM）100 ns · 8–64 GB
硬盘（SSD / HDD）150 μs ~ 10 ms
把鼠标移到任意一层，看它的细节。
关键不是数字本身，而是：访问 L1 只要约 4 个周期，缓存未命中则要停滞几百个周期。同一个「O(1) 访问」，命中与未命中差了几百倍——这就是下面要说的「单次操作代价」。

02把 O(n) 拆开

大 O 记的是基本操作的执行次数。但它被叫成「时间复杂度」，漏掉了最关键的一项。
真实耗时 ≈ 操作次数（大 O） × 单次操作代价
O(n)、O(log n) 数的是「操作多少次」——这一项大 O 管住了。
但每次操作到底要几个周期、会命中缓存还是未命中——这一项大 O 看不见，却被「时间复杂度」这个名字糊弄过去了。
数组遍历里的 O(1) 访问，和链表遍历里的 O(1) 访问，代价能差几百倍。这就是下面四个实验要展示的。

03实验一：数组遍历 vs 链表遍历

两者都是 O(n)，访问了同样多的元素。但数组连续、链表跳跃，缓存命中率天差地别。
小样本看过程（16 个元素，一个缓存行）
步 0 / 0

数组（顺序访问）

16 个 int 挤在一个缓存行里，一次搬运全带进来

链表（跳跃访问）

节点散落各处，下一个地址藏在 next 指针里
绿 = 缓存命中，红 = 未命中，黄 = 正在访问

04实验二：快速排序 vs 归并排序

同为 O(n log n)，但快排顺序访问 + 原地交换，归并两个子数组交替访问还要再复制一遍。不同数据分布下，差距还会变。
小样本看过程（20 个元素）
步 0 / 0

快速排序（partition）

两个指针从两端向中间扫，原地交换

归并排序（自底向上）

小块并成大块，还要复制到辅助数组
紫 = pivot，黄 = 正在操作，红 = 交换/复制，绿 = 已排好

05实验三：矩阵遍历 行优先 vs 列优先

都是 O(n²)，但行优先顺着内存走，列优先每一跳都跨过一整行。空间局部性最干净的演示。
小样本看过程（8×8，每行 8 个 double = 64 字节 = 一个缓存行）
步 0 / 0

行优先

一次搬一整行，同行后续都命中

列优先

每次跳一行，几乎每次都未命中
黄 = 正在访问，绿 = 命中，红 = 未命中，蓝框 = 缓存行已加载

06实验四：二分查找 vs 线性查找

二分 O(log n) 次数少，但访问跳跃、易未命中；线性 O(n) 次数多，但顺序访问命中率高。小规模下，线性甚至可能反超。
小样本看过程（16 个元素）
步 0 / 0

线性查找

顺序访问，命中率高

二分查找

跳跃访问，频繁换缓存行
黄 = 正在访问，绿 = 已访问（命中），紫 = 命中目标