01 绪论与复杂度
磨刀不误砍柴工：这一篇解决两个元问题——结构怎么分类（逻辑 vs 存储），以及程序怎么算快慢（复杂度分析）。后者是后面每一篇都会用到的"度量衡"。
一、基本概念：四件事串成一句话
数据 → 由数据元素组成 → 元素由数据项组成 → 元素间有数据元素关系（结构）
- 数据项是最小单位（如学生的"姓名"字段）；数据元素是基本单位（一个学生记录）
- 数据对象：性质相同的数据元素的集合（如"全体学生"）
- 数据结构：互相之间存在特定关系的数据元素的集合 = 元素集 + 关系集 + 运算集
逻辑结构 vs 存储结构（408 第一道选择题常客）
逻辑结构——数据元素间的关系，与存储无关：
集合（无序无重复）
线性结构：一对一（线性表、栈、队列、串）
树形结构：一对多（二叉树、B 树）
图形结构：多对多（有向图、无向图）
存储结构（物理结构）——逻辑结构在内存里的落法：
| 存储结构 | 思想 | 适用 |
|---|---|---|
| 顺序存储 | 一段连续内存，靠位置表相邻 | 查多改少 |
| 链式存储 | 结点 + 指针，靠指针表相邻 | 增删多 |
| 索引存储 | 附加索引表（关键字 → 地址） | 数据库、字典 |
| 散列存储 | 哈希函数直接算地址 | 等值查找 |
⚠️ 核心认知：同一个逻辑结构可以用不同存储结构实现（线性表既能顺序也能链式）；运算的定义在逻辑结构上，运算的实现依赖存储结构。
二、算法五特性与好算法目标
算法五特性（背）：有穷性、确定性、可行性、输入（≥0 个）、输出（≥1 个）。
⚠️ "有穷"是算法和程序的区分点：程序（如操作系统）可以不终止，算法必须有限步结束。
好算法四目标：正确性、可读性、健壮性、高效性（时间 + 空间）——高效性就是复杂度分析要量化的东西。
三、时间复杂度：数"基本操作的次数"
从语句频度到大 O
三步走：
- 找出基本操作（最深嵌套里的那条语句）
- 数它的执行次数 f(n)（问题规模 n 的函数）
- 取最高阶项、扔系数 → 大 O
int sum = 0;
for (int i = 1; i <= n; i++) // n 次
for (int j = 1; j <= n; j++) // n 次
sum++; // 基本操作 → f(n) = n² → O(n²)
常见复杂度阶梯（从小到大）
\[O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\]
💡 感性记法：n=10⁶ 时——O(n) 百万次（毫秒级）；O(n log n) 约两千万次（几十毫秒）；O(n²) 万亿次（小时级）。排序为什么折腾 O(n log n)，看这张表就懂。
大 O 推导规则（408 选择题考点）
- 加法规则：\(T_1 + T_2 = O(\max(f_1, f_2))\)——只留最大项
- 乘法规则：\(T_1 \times T_2 = O(f_1 \times f_2)\)——嵌套循环相乘
- 常数和低阶全扔：O(3n² + 100n + 5) = O(n²)
典型例子（能手推才算会）
| 代码片段 | 复杂度 | 解释 |
|---|---|---|
while (i <= n) i *= 2; |
O(log n) | 每轮翻倍，走 log₂n 轮 |
while (n > 1) n /= 2; |
O(log n) | 同上，折半家族 |
| 外层 i 从 1 到 n 乘 2，内层 O(n) | O(n log n) | 归并/堆排的骨架 |
递归 f(n) = f(n-1) + f(n-2) 裸写 |
O(2ⁿ) | 调用树节点数指数爆炸（记忆化后 O(n)） |
三种情况复杂度
- 最好/最坏/平均：如顺序查找分别是 O(1)/O(n)/O(n/2)=O(n)
- 408 题面说"平均时间复杂度"时要乘概率权重（如成功查找 ASL）
- 均摊（摊还）分析：偶尔很贵、总体便宜——如动态数组扩容，单次 O(n) 但均摊 O(1)
四、空间复杂度：额外开了多少
S(n) = 算法额外占用的辅助空间随 n 的增长。
| 场景 | 空间复杂度 |
|---|---|
| 原地快排（递归栈深 log n） | O(log n) |
| 归并排序的辅助数组 | O(n) |
| 图的邻接矩阵 | O(n²) |
| 迭代两变量求斐波那契 | O(1) |
⚠️ 空间复杂度不含输入数据本身；递归的栈深算在内——"递归版快排空间 O(log n)"指的是栈。
五、时间换空间、空间换时间
- 空间换时间：哈希表（O(n) 空间换 O(1) 查找）、记忆化递归、前缀和——后端工程默认取向
- 时间换空间：流式处理、原地排序、位图压缩——内存受限场景（嵌入式、外部排序）
- 没有免费午餐：O(1) 查找的哈希表，最坏仍可能 O(n)（全冲突），所以工程上还要看期望性能
六、盲点自测
- 逻辑结构和存储结构谁与"计算机"有关？（存储结构；逻辑结构是数学关系）
- 栈和队列属于什么逻辑结构？（线性——一对一）
for (i=1; i<=n; i*=2) sum++;复杂度？（O(log n)）- 大 O 的加法/乘法规则各是什么？（取 max / 相乘）
- 算法与程序的根本区别？（有穷性）
- 递归算法的空间复杂度看什么？（递归深度——栈帧）
- 均摊 O(1) 是什么意思？（最坏偶尔 O(n)，摊到每次操作平均 O(1)）
七、动手玩
# 亲眼看看 O(n) vs O(n log n) vs O(n²) 的差距
import time, random
def timeit(fn, arr):
t = time.perf_counter()
fn(arr)
return time.perf_counter() - t
arr = [random.random() for _ in range(100000)]
print('sorted (Timsort, O(n log n)):', timeit(lambda a: sorted(a), arr))
arr2 = arr[:5000]
def bubble(a): # O(n²)
for i in range(len(a)):
for j in range(len(a)-i-1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print('bubble O(n²) on 5000 elements:', timeit(bubble, arr2))
# 十倍的数据，平方复杂度是一百倍的时间——亲手感受
参考资料
- 王道《数据结构考研复习指导》第 1 章
- 《算法图解》——复杂度的漫画版入门
- 刷题理模型——复杂度分析在实战题里的用法
💬 评论