![](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="32" height="32"><text y="28" font-size="28">🤑</text></svg>)
01 复杂度分析 — 算法的「CPI 指数」
李永乐式比喻：你要从北京去上海——
- 时间复杂度 = 需要多少时间（坐飞机 2h vs 步行 30天）
- 空间复杂度 = 需要带多少行李（轻装简行 vs 搬家式旅行）
- 好的算法 = 花最少的时间 + 用最少的空间，但往往二者不可兼得
英文 -> 中文 -> 本质映射
| 英文术语 | 中文 | 本质定义 | 李永乐类比 |
|---|---|---|---|
| Time Complexity | 时间复杂度 | 随数据量 n 增长，指令执行次数的增长趋势 | 食堂排队：队伍越长，你打饭的时间怎么变？ |
| Space Complexity | 空间复杂度 | 随数据量 n 增长，内存占用的增长趋势 | 做菜需要多大厨房 |
| Big O Notation | 大O表示法 | 忽略常数项，只关注增长趋势 | 不说"多花3分钟"，说"多花的时间跟排队人数成正比" |
| O(1) | 常数时间 | 不管数据多大，耗时固定 | 直接拿你的专用饭盒 |
| O(log n) | 对数时间 | 每操作一次，数据规模减半 | 猜数字：100->50->25->12->6->3->1 |
| O(n) | 线性时间 | 耗时和数据量成正比 | 挨个数一遍人头 |
| O(n log n) | 线性对数时间 | 分小块处理后合并 | 全班分组打扫卫生再汇总 |
| O(n^2) | 平方时间 | 双重循环，每个元素跟其他所有比 | 每个人跟所有人握手 |
复杂度 -> 硬件映射
复杂度对比（100 万条数据）
| 复杂度 | 指令数 | 耗时估算 | 业务感受 |
|---|---|---|---|
| O(1) | 1 条 | 纳秒级 | 瞬间 |
| O(log n) | ~20 条 | 纳秒级 | 瞬间 |
| O(n) | 100 万条 | ~1-5ms | 几乎无感 |
| O(n log n) | ~2000 万条 | ~20-100ms | 可感知但可接受 |
| O(n^2) | 1 万亿条 | ~17 分钟 | 不可接受 |
| O(2^n) | 宇宙年龄级 | 不可计算 | 不可行 |
关键判断：O(n^2) 在数据量超过 1 万时基本不可用。数据量翻 10 倍，时间慢 100 倍。
内存占用对比
| 数据 | 存储方式 | 内存占用 | 结论 |
|---|---|---|---|
| 100 万整数 | 数组 O(n) | ~8 MB | 可接受 |
| 1000x1000 矩阵 | 二维数组 O(n^2) | ~8 MB | 可接受 |
| 10 个元素全排列 | 全部存储 O(n!) | ~100 MB | 需要关注 |
| 10 万节点 | 邻接矩阵 O(v^2) | ~40 GB | 不可行，需用邻接表 |
企业场景：用复杂度做技术决策
| 业务场景 | 数据规模 | 不可用算法 | 推荐算法 | 原因 |
|---|---|---|---|---|
| 电商商品搜索 | 1000 万商品 | 线性查找 O(n) | B+ 树索引 | O(log n) vs O(n)，效率差 50 万倍 |
| 用户订单排序 | 10 万条 | 冒泡排序 O(n^2) | 归并排序 O(n log n) | 100 亿次 vs 170 万次 |
| 实时 Top 10 | 1000 万用户 | 全排序 O(n log n) | 堆排序 O(n log k) | 只维护 10 个元素 |
| 地图导航 | 1 亿节点 | DFS 全路径搜索 | A* 启发式搜索 | 剪枝降低搜索空间 99.9% |
AI 协作
AI 能做的：
- 分析任意代码的时间/空间复杂度
- 给出 O(n^2) -> O(n log n) 的优化建议
- 生成复杂度测试代码
人类需决策的：
- 当前业务是 CPU 瓶颈还是内存瓶颈？
- 允许用空间换时间吗？（如加缓存）
- 100ms 延迟和 100MB 内存，哪个成本更高？