适用读者：写得出代码，但面对"该用数组还是链表/哈希还是树"时靠感觉的人。本系列第一篇。
前置：S02（对 RTT/吞吐有量级直觉即可）。
实测环境：Ubuntu 24.04.1 / Python 3.12.3 / JDK 21（后文对比）；实测日期 2026-11-05。
覆盖旧文：A-1497（数据结构总览，56 点）、A-1884（学习路线，140 点）、A-521（数据契约，34 点）= 230 点。
覆盖扩展：E-S03-001（渐进/最坏/摊还三种口径）。
下一篇：S03-B02 · 数组与链表。
1. 一句话结论
复杂度不是"精确耗时"，是"输入变大时耗时的增长形状"。
三种口径必须分清，否则讨论永远吵架：
| 口径 | 回答的问题 | 例子 |
|---|---|---|
| 最好 / 平均 / 最坏 | 同一算法的不同输入 | 快排最坏 O(n²)，平均 O(n log n) |
| 渐进（大 O） | 输入趋于无穷时的上界 | O(n)、O(n log n) |
| 摊还（amortized） | 一串操作的平均代价 | 动态数组扩容：单次 O(n)，摊还 O(1) |
"这段代码是 O(n) 还是 O(n²)"的争论，八成是因为没说清是哪一种口径。
2. 实测：增长形状比常数重要
同一台机器上跑两类函数（Python 3.12.3）：
def f_n(n): # O(n)
s = 0
for i in range(n): s += i
def f_n2(n): # O(n²)
s = 0
for i in range(n):
for j in range(n): s += 1
| n | O(n) | O(n²) | 比值 |
|---|---|---|---|
| 1,000 | 0.08 ms | 103.04 ms | 1,242× |
| 2,000 | 0.15 ms | 395.77 ms | 2,572× |
| 4,000 | 0.43 ms | 1,729.97 ms | 3,985× |
读法：n 翻倍，O(n) 的耗时约翻倍；O(n²) 的耗时约 ×3.8–4.4（理论 4×）。
这条数据解释了为什么"复杂度"值得单独学：n=1 万时，那 1,700 ms 会变成 10 秒以上；n=10 万就是几分钟。常数因子救不了量级差异。
3. 常见复杂度与"能扛多大"
| 复杂度 | n=1e3 | n=1e5 | n=1e7 | 典型 |
|---|---|---|---|---|
| O(1) | 立即 | 立即 | 立即 | 哈希查找、数组下标 |
| O(log n) | ~10 步 | ~17 步 | ~24 步 | 二分、平衡树 |
| O(n) | 1e3 | 1e5 | 1e7 | 单次遍历 |
| O(n log n) | ~1e4 | ~1.7e6 | ~2.3e8 | 排序 |
| O(n²) | 1e6 | 1e10 ❌ | — | 双层循环 |
| O(2ⁿ) | ❌ | ❌ | ❌ | 暴力枚举（n>25 就危险） |
工程判据：每秒约 1e8 次简单操作（现代 CPU 的量级）。用这个数就能估算"我的算法能不能在 1 秒内跑完"。
4. 数据结构总览：按"操作"选，不按"名字"选
| 结构 | 随机访问 | 插入/删除 | 查找 | 有序遍历 | 典型用途 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n)（中间） | O(n) | ✅ | 密集存储、缓存友好 |
| 链表 | O(n) | O(1)（已知位置） | O(n) | ✅ | 频繁插入删除、LRU |
| 栈 | 仅栈顶 | O(1) | — | — | 表达式求值、括号匹配、DFS |
| 队列 | 仅队头 | O(1) | — | — | BFS、任务队列 |
| 哈希表 | — | O(1) 平均 | O(1) 平均 | ❌ 无序 | 去重、计数、索引 |
| 堆 | 仅堆顶 | O(log n) | — | 部分有序 | Top-K、定时器、优先队列 |
| BST/平衡树 | O(log n) | O(log n) | O(log n) | ✅ 有序 | 范围查询、有序索引 |
| Trie | — | O(L) | O(L) | ✅ 字典序 | 前缀搜索、自动补全 |
| 图 | — | — | — | — | 关系网络、路径、连通性 |
| 并查集 | — | — | 近似 O(1) | — | 连通性、分组 |
4.1 选型三问（按顺序问）
① 需要"有序"吗？
├── 不需要 → 哈希表（O(1) 平均）
└── 需要 → ② 需要"范围查询"还是只要"最小/最大"？
├── 只要极值 → 堆
└── 范围/前驱后继 → 平衡树 / 有序数组 + 二分
③ 是否需要频繁在中间插入删除？
├── 是 → 链表（但要考虑 cache 惩罚，见 B02）
└── 否 → 数组
5. 关于"数据契约"（旧文 A-521 的重组）
旧文 A-521 的观点值得保留：先定数据结构，再让模块按它协作。
| 层次 | 决定什么 | 后果 |
|---|---|---|
| 数据契约（结构 + 不变式） | 字段含义、允许的状态、边界 | 定错 → 下游全部返工 |
| 算法 | 在这个结构上怎么操作 | 可优化 |
| 实现 | 具体语言与容器 | 可替换 |
判据："换个语言重写，数据结构会变吗？" 会 → 那是实现细节；不会 → 那是契约，要写进文档。
6. 学习路线（旧文 A-1884 的重排）
| 阶段 | 内容 | 对应正文 |
|---|---|---|
| 第 1 周 | 复杂度与基础结构（数组/链表/栈/队列） | B01–B03 |
| 第 2 周 | 哈希、堆、树家族 | B04–B06 |
| 第 3 周 | 图、并查集、位运算 | B07–B08 |
| 第 4 周 | 数学算法与工程用途 | B09 |
| 第 5 周起 | 题解训练（双指针 → 二分 → 链表 → 回溯 → DP → 单调栈） | X01、J01–J06 |
| 收尾 | 题库设计与对拍 | A01–A02 |
原则：每种结构配一个"能跑的实现 + 一组边界用例"，不要只看图。
7. 五个误区
| 误区 | 真相 |
|---|---|
| "O(1) 一定比 O(n) 快" | 小 n 时常数因子占主导（如 n=10 时哈希可能比遍历慢） |
| "复杂度低就万事大吉" | 空间、cache、GC、常数都在影响真实性能（B02） |
| "链表插入一定是 O(1)" | 只有"已知位置"才是；找位置本身是 O(n) |
| "哈希表查找永远 O(1)" | 平均是；最坏 O(n)（全部冲突） |
| "摊还 O(1) 就是每次都快" | 个别操作仍可能 O(n)（扩容那一次） |
8. 自检
- 说出"最好/平均/最坏/摊还"四个口径的区别，各举一例。
- n 从 1e5 到 1e6，O(n log n) 的耗时大约增加几倍？
- 给定"高频插入 + 偶尔按 key 查"，你会选什么结构？为什么？
- 为什么"数据契约"比"数据结构实现"更该写进文档？
- 用"每秒 1e8 次操作"估算：n=1e6 的 O(n²) 算法大概要跑多久？
9. 下一篇
S03-B02 · 数组与链表：连续与分散的代价
下一篇用同一台机器上的实测（ArrayList 头插 535.9 ms vs 尾插 22.6 ms；LinkedList.get(i) 遍历 6,163 ms vs 数组 15.9 ms）说明：理论复杂度相同的东西，在真实机器上可能差两个数量级——原因在内存布局与缓存。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1497/1884/521；扩展点 E-S03-001。增长实测为 2026-11-05（Python 3.12.3）。