complexity - memory
01. 复杂度、内存与数据访问成本
0. 本章先解决什么问题
学习数据结构时,最容易背成:
数组查询 O(1)
链表插入 O(1)
哈希表平均 O(1)
树 O(log n)
这些结论有用,但不够。真实程序里还要问:
- O(1) 的常数有多大?
- 数据在内存里连续还是分散?
- 是否会触发扩容?
- 是否 cache 友好?
- 最坏情况会不会退化?
- 操作频率是什么?
- 内存多占一点能不能换速度?
本章建立数据结构的成本模型。后面每个结构都用这套模型分析。
先看复杂度之外的成本:内存布局、常数项和峰值抖动会让同样的大 O 表现完全不同。
这张图怎么读
先看大 O,它描述规模增长趋势;再看常数项、内存访问模式、缓存命中和分配成本,它们决定真实机器上的体感速度。两个算法同样是 O(n),如果一个顺序扫连续数组,另一个追逐分散指针,CPU cache、预取和内存延迟会让结果差很多。读复杂度时要把“数学增长”和“硬件成本”同时放在脑子里。
1. 复杂度是什么
复杂度描述的是:
当输入规模 n 增大时,操作成本如何增长。
常见复杂度:
| 复杂度 | 直觉 | 例子 |
|---|---|---|
| O(1) | 不随 n 增长 | 数组按下标访问 |
| O(log n) | 每次缩小一部分范围 | 二分查找、平衡树查找 |
| O(n) | 扫一遍 | 顺序查找 |
| O(n log n) | 分治排序常见 | 归并排序、堆排序 |
| O(n^2) | 两层遍历 | 朴素两两比较 |
复杂度关注增长趋势,不关注具体机器、语言、常数和缓存。
机制深挖:大 O 省略了哪些前提
大 O 是必要工具,但它故意省略了很多现实细节。省略本身没错,问题是读者不能忘记它省略了什么。
| 被省略的因素 | 为什么重要 |
|---|---|
| 常数项 | 一次哈希、一次比较、一次内存分配都可能很贵 |
| 数据分布 | 平均情况依赖输入是否接近假设 |
| 内存层次 | cache miss 和顺序访问差距巨大 |
| 分支可预测性 | 同样的循环,数据模式不同会影响流水线 |
| 分配/回收 | 节点结构可能把成本转移到内存管理 |
| 峰值延迟 | 摊还快不代表每一次都快 |
| 并发争用 | 理论操作快,但锁竞争会改变成本 |
因此复杂度结论应该读成一句带条件的话:
在某些输入假设、成本模型和实现条件下,
当 n 增大时,主要增长项是什么?
这句话比单独背 O(1)、O(log n) 更接近真实工程。
2. 最好、平均、最坏
同一个操作可能有不同情况。
例如在数组中查找某个值:
| 情况 | 成本 |
|---|---|
| 第一个就是 | O(1) |
| 平均扫一半 | O(n) |
| 不存在或最后一个 | O(n) |
哈希表也类似:
| 情况 | 成本 |
|---|---|
| 冲突少 | 平均接近 O(1) |
| 冲突严重 | 可能退化到 O(n) 或更差 |
学习时要问:
这个结论是最好、平均,还是最坏?
依赖什么假设?
3. 摊还复杂度:一次贵不代表每次贵
动态数组扩容时很贵,因为要搬迁所有元素。
但扩容不是每次插入都发生。
假设容量满了就翻倍:
容量 4 -> 8 -> 16 -> 32
大多数尾部插入只做:
把新元素放到末尾
少数插入触发:
申请更大空间
复制旧元素
插入新元素
把扩容成本分摊到多次插入上,尾部追加的摊还成本仍然接近 O(1)。
摊还分析适合:
- 动态数组扩容。
- 栈/队列批量迁移。
- 某些懒删除和重建结构。
4. 空间复杂度和额外空间
空间复杂度描述额外占用。
| 结构 | 空间特点 |
|---|---|
| 数组 | 元素连续,额外开销少 |
| 链表 | 每个节点要额外保存指针 |
| 哈希表 | 桶数组可能有空位 |
| 树 | 每个节点保存子指针或索引 |
| 图邻接表 | 顶点和边都要存储 |
| 位图 | 用 bit 压缩布尔状态 |
空间不是免费资源。空间多会带来:
- 内存占用高。
- Cache 容量压力。
- 分配和回收成本。
- 复制和序列化成本。
但有时多用空间能换速度,比如哈希表用桶数组换快速查找。
5. 内存连续性和缓存
复杂度相同,内存布局不同,实际速度可能差很多。
连续数组:
[a0][a1][a2][a3][a4]
分散节点:
node1 -> node2 -> node3
CPU 读取内存时常按 cache line 搬一整块。数组顺序访问能利用空间局部性;链式结构频繁跳转,容易 cache miss。
所以:
O(n) 顺序扫描连续数组
可能比 O(n) 遍历链表快很多。
复杂度告诉你规模趋势,缓存告诉你真实常数。
6. 指针成本
指针让结构灵活,但也有成本:
| 成本 | 解释 |
|---|---|
| 额外空间 | 每个节点保存一个或多个地址 |
| 分配成本 | 节点通常单独申请 |
| cache miss | 节点可能分散 |
| 维护复杂 | 插入删除要更新多个引用 |
| 错误风险 | 断链、成环、悬挂引用 |
链表、树、图都大量依赖指针或引用。它们的优势是结构灵活,代价是局部性和维护复杂度。
反例:O(log n) 不一定总比 O(n) 快
如果只按复杂度排序,很容易得出:
O(log n) 一定比 O(n) 快
这在 n 足够大时通常方向正确,但在真实机器上不总是立刻成立。
例如两个查找任务:
| 方案 | 复杂度 | 真实访问模式 |
|---|---|---|
| 在小数组里顺序扫描 | O(n) | 连续内存、分支简单、cache 友好 |
| 在树里查找 | O(log n) | 多次指针跳转、可能 cache miss、比较路径不连续 |
当数据量很小,或者数组正好在 cache 里,顺序扫描可能更快。这个反例不是否定复杂度,而是提醒你分层判断:
先用复杂度判断增长趋势
再用常数、cache、数据规模判断当前场景
最后用测量验证
这也是为什么很多系统会在小规模时用简单数组,规模变大后才切换到树、哈希表或索引结构。
7. 比较成本、哈希成本和相等判断
数据结构操作常常不是“免费比较”。
排序需要比较:
比较两个元素大小
哈希表需要:
计算 key 的哈希值
判断 key 是否相等
如果 key 很长,比如长字符串,哈希和比较本身就有成本。
所以哈希表“平均 O(1)”通常隐含:
哈希计算和相等判断成本可接受。
如果 key 很复杂,真实成本可能接近:
O(key_length)
8. 修改成本和搬迁成本
插入删除不只看“位置是否能改”。
数组中间插入:
[a][b][c][d]
在 b 前插入 x
-> b,c,d 后移
链表中间插入:
prev -> next
变成 prev -> x -> next
但链表要先找到 prev,这个查找可能 O(n)。
修改成本要拆开:
定位成本 + 实际修改成本 + 维护不变量成本
树插入还要维护平衡。堆插入要上浮。哈希表插入可能触发扩容。
9. 退化、抖动和峰值成本
平均快不代表每次都快。
常见峰值:
| 结构 | 峰值来源 |
|---|---|
| 动态数组 | 扩容时搬迁 |
| 哈希表 | rehash 时重分布 |
| 树 | 重平衡 |
| 堆 | 上浮/下沉 |
| 图 | 大量边遍历 |
| 队列 | 消费跟不上,队列堆积 |
如果系统对延迟敏感,一次 O(n) 扩容也可能造成明显卡顿。
这就是为什么要区分:
- 平均吞吐。
- 单次尾延迟。
- 最坏情况。
10. 联系实际:如何读一个数据结构的性能声明
看到一个结构的复杂度表,不要停在表面。
按这个顺序追问:
- 这个复杂度是平均、摊还还是最坏?
- key 的比较或哈希成本是否算进去了?
- 数据是否连续?
- 是否需要额外指针和对象?
- 插入删除是否会移动大量元素?
- 是否会扩容、重建、重平衡?
- 是否需要保持有序?
- 是否支持范围查询?
- 高并发下是否会争用同一结构?
- 内存是否足够,cache 是否友好?
这套问题比死背复杂度更实用。
练习卡:同样 O(1),真实成本可能差很多
比较两个“常数时间”操作:
| 操作 | 大 O | 真实成本可能来自 |
|---|---|---|
| 访问连续数组的下一个元素 | O(1) | 地址计算简单、缓存命中率高 |
| 沿指针跳到下一节点 | O(1) | 随机内存、缓存未命中、额外对象开销 |
| 哈希查找一次 | 平均 O(1) | 哈希计算、冲突链、扩容、相等比较 |
| 队列入队一次 | O(1) | 锁、内存分配、环形缓冲区是否满 |
练习方式:看到一个复杂度声明时,在旁边补三列:常数项来自哪里、最坏情况是什么、是否会造成峰值抖动。这样你会把复杂度当作第一层筛选,而不是最终性能结论。
11. 学完本章你能解决什么问题
学完这一章,你应该能解决或开始分析这些问题:
- O(1)、O(log n)、O(n) 各代表什么趋势?
- 为什么最好、平均、最坏情况要分开看?
- 摊还复杂度为什么能解释动态数组尾插接近 O(1)?
- 为什么连续内存通常更 cache 友好?
- 指针结构有哪些隐藏成本?
- 哈希和比较本身为什么也可能成为成本?
- 为什么平均快的结构仍可能有单次抖动?
- 如何从时间、空间、缓存、退化、操作频率综合判断数据结构?
复杂度是入口,不是终点。真正的数据结构分析要把数学增长趋势和机器上的访问成本连起来。