数据结构与算法之美 · 深度学习指南（细化样板）
作者：王争（前 Google 工程师）｜ 极客时间最经典算法课 真实结构：56 讲正文（含 10 讲算法实战）+ 4 期不定期福利 + 春节 7 天练 本指南按课程真实讲次提炼，融入每一讲的核心知识点 + 课程原案例 + 思考题，并标注了每讲「学完要能回答的问题」。
0. 这门课到底讲什么（课程自述）
课程开篇就点破了一件事：数据结构和算法解决的是「快」和「省」的问题——让代码跑得更快、更省存储空间。而王争老师反复强调的一句核心判断是：
「复杂度分析是整个算法学习的精髓，掌握了它，数据结构和算法的内容基本上就掌握了一半。」
所以这门课不是「背数据结构」，而是「建立一套分析问题、评估效率的思维模型」。学完的终极目标是——遇到任何系统，都能看出它底层用了什么数据结构和算法。
1. 模块一：开篇 + 复杂度分析（第 1–4 讲）
| 讲次 | 核心知识点 | 课程原案例 / 金句 |
|---|---|---|
| 01 为什么要学 | 算法是内功，直接决定性能天花板；大厂面试必考 | 「5 秒 vs 0.001 秒的差距，就是算法和不会算法的差距」 |
| 02 怎么高效学 | 20 个知识点 + 10 个算法；边学边练边刷题 | 抓住重点：线性表、树、图、排序、查找、哈希、字符串、贪心/分治/回溯/DP |
| 03 复杂度分析（上） | 大 O 表示法；事后统计法两大局限（依赖环境、依赖数据规模） | 求 1+2+…+n 的代码：i9 比 i3 快、数据有序时排序「不用做任何操作」 |
| 04 复杂度分析（下） | 最好 / 最坏 / 平均 / 均摊 四种复杂度；均摊分析法 | 数组插入扩容的「均摊」分析（偶尔一次 O(n)，摊到每次仍是 O(1)） |
引发思考：
- 为什么「把代码跑一遍测时间」不能替代复杂度分析？（环境 + 数据规模两大局限）
O(1)真的代表「只执行一次」吗？它和「常数级」的准确含义是什么？- 均摊复杂度用在什么场景？和「平均复杂度」的区别在哪？
2. 模块二：线性结构（第 5–10 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 05 数组 | 随机访问 O(1)；数组从 0 编号是为了寻址少一次减法 | a[k] 地址 = base + k×type_size（若从 1 开始则多减一次） |
| 06 链表（上） | 单向/双向/循环链表；用链表实现 LRU 缓存淘汰 | LRU：新访问的放头部，满时淘汰尾部 |
| 07 链表（下） | 写对链表代码的 6 个技巧 | 理解指针含义、警惕丢失指针、利用哨兵节点简化 |
| 08 栈 | 后进先出；浏览器前进/后退的双栈实现 | 后退栈 + 前进栈，前进后退就是两个栈互相倒数据 |
| 09 队列 | 先进先出；线程池等有限资源池用队列 | 有界队列处理「生产者快、消费者慢」的缓冲 |
| 10 递归 | 递归三要素（终止条件/递推公式/返回值）；警惕堆栈溢出 | 三行代码找「最终推荐人」（递归查上级，注意环导致死循环） |
引发思考：
- 为什么数组查询快、插入慢，链表正相反？根本原因是「连续存储 vs 链式存储」？
- 浏览器前进后退，为什么单栈做不了、必须双栈？
- 递归的「堆栈溢出」在阶段一《内存知识》里对应哪块内存？怎么用「尾递归/迭代」规避？
3. 模块三：排序与查找（第 11–16 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 11 排序（上） | 冒泡/插入/选择；插入比冒泡更受欢迎（交换次数少） | 三种 O(n²) 排序的稳定性与移动次数对比 |
| 12 排序（下） | 归并 O(nlogn) 稳定、快排 O(nlogn) 不稳定；快排思想 O(n) 找第 K 大 | 分治 + 分区，一遍 partition 定位第 K 大 |
| 13 线性排序 | 桶排序/计数排序/基数排序 O(n)；按年龄给 100 万用户排序 | 年龄范围小 → 计数排序，O(n) 秒排 |
| 14 排序优化 | 通用排序函数怎么实现（业界：快排 + 小数据插排 + 三数取中） | C 的 qsort、Java 的排序是怎么组合算法的 |
| 15 二分查找（上） | 二分 O(logn)；最省内存的查找（只依赖数组下标） | 递归/非递归二分，警惕三个易错点 |
| 16 二分查找（下） | 二分变体；快速定位 IP 对应省份 | 查「最后一个小于等于目标值」的变体二分 |
引发思考：
- 为什么插入排序比冒泡排序「更受欢迎」？（同 O(n²)，但移动/交换成本更低）
- 线性排序（计数/桶/基数）为什么能突破 O(nlogn) 下限？它牺牲了什么？（数据范围）
- 二分查找的三个经典 bug 是什么？（循环条件、mid 取值、low/high 更新）——手写一遍看看会不会错。
4. 模块四：跳表 + 散列表 + 哈希（第 17–22 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 17 跳表 | 链表加索引实现 O(logn)；Redis 有序集合为什么用跳表不用红黑树 | 跳表实现简单、支持按区间查（zrange） |
| 18 散列表（上） | 散列函数、哈希冲突（开放寻址/链表法）；Word 拼写检查 | 散列表 = 数组 + 散列函数，O(1) 查单词 |
| 19 散列表（中） | 打造工业级散列表：装载因子、动态扩容、高效散列函数 | 装载因子过大触发扩容，扩容时数据搬迁 |
| 20 散列表（下） | 散列表 + 链表 = LRU / LinkedHashMap | Java LinkedHashMap 用双向链表维护插入/访问顺序 |
| 21 哈希算法（上） | 哈希算法四大要求；防止用户信息脱库（加盐哈希） | 密码不能明文/简单哈希存，要加盐 + 慢哈希 |
| 22 哈希算法（下） | 哈希在分布式系统中的应用 | 负载均衡、分片、一致性哈希、分布式存储 |
引发思考：
- Redis 的 Sorted Set 底层为什么是「跳表 + 字典」组合？只用一个行不行？
- 哈希冲突的「开放寻址」和「链表法」各自适合什么场景？（数据量、缓存友好性）
- 为什么说「加盐哈希」能对抗彩虹表攻击？盐应该存哪？
- 一致性哈希为什么能解决「加机器导致缓存大量失效」？（和阶段七分布式联动）
5. 模块五：树（第 23–29 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 23 二叉树（上） | 完全二叉树、什么样的树适合数组存储 | 完全二叉树用数组存（下标 i 的孩子是 2i、2i+1） |
| 24 二叉树（下） | 二叉查找树；有了散列表为什么还要树 | 散列表无序、扩容慢，树支持有序遍历和范围查 |
| 25 红黑树（上） | 工程中都爱用红黑树：近似平衡、增删改查稳定 O(logn) | 平衡二叉树 vs 红黑树的取舍 |
| 26 红黑树（下） | 红黑树的左旋/右旋、变色；实现技巧 | 「实现红黑树的几个诀窍」 |
| 27 递归树 | 用递归树求递归复杂度 | 归并、快排的递归树画法，替代主定理 |
| 28 堆 | 堆的插入/删除；堆排序为什么没快排快 | 堆排序访问不连续（缓存不友好） |
| 29 堆的应用 | Top10 热门搜索词（小顶堆） | 维护一个 10 元素小顶堆，O(nlog10) |
引发思考：
- 「完全二叉树用数组存」和「堆用数组存」是同一件事吗？下标父子关系是什么？
- 红黑树、AVL、跳表，各自「牺牲了什么换来了什么」？
- 堆排序不如快排快，为什么？「缓存友好性」在阶段一《内存知识》里对应什么概念？（局部性原理）
6. 模块六：图（第 30–31 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 30 图的表示 | 邻接矩阵 vs 邻接表；微博/微信好友关系怎么存 | 社交网络稀疏图用邻接表（或反向邻接表存粉丝） |
| 31 搜索 | BFS / DFS；三度好友关系 | 从你出发 BFS 三层，找出三度好友 |
引发思考：
- 微博（大 V 粉丝千万）和微信（双向好友），图的存储结构怎么选？
- BFS 为什么用队列、DFS 为什么用栈（或递归）？「最短路径」为什么必须 BFS？
7. 模块七：字符串匹配（第 32–36 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 32 字符串（上） | 用哈希做高效字符串匹配（RK 算法） | 先比对哈希值，相同再逐字符确认 |
| 33 字符串（中） | 文本编辑器查找功能（BM 算法：坏字符 + 好后缀） | 从右往左匹配，坏字符规则快速后移 |
| 34 字符串（下） | KMP 算法（好前缀规则） | BM 理解后，KMP 的 next 数组就通了 |
| 35 Trie 树 | 搜索引擎关键词提示（前缀树） | 输入「你」提示「你好」「你在干什么」 |
| 36 AC 自动机 | 多模式串匹配 → 敏感词过滤 | Trie + KMP 的失败指针，一次扫描匹配多个模式 |
引发思考：
- BM 和 KMP 的核心思想差在哪？（坏字符 vs 好前缀，谁更适合实际工程）
- Trie 树解决什么问题？它和散列表比，在「前缀匹配」上强在哪？
- 敏感词过滤为什么要用 AC 自动机，而不是把每个词都跑一遍 KMP？
8. 模块八：高级算法思想（第 37–42 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 37 贪心 | 贪心算法 + 霍夫曼编码 | Huffman 压缩编码（频率高的用短码） |
| 38 分治 | 分治思想 | MapReduce 的大规模计算（分而治之） |
| 39 回溯 | 回溯 = 深度优先 + 撤销选择 | 电影《蝴蝶效应》类比；八皇后、0-1 背包 |
| 40 初识 DP | 动态规划入门 | 双十一购物凑单（满减最优组合） |
| 41 DP 理论 | 最优子结构、无后效性、重复子问题 | 三个特性是「能不能用 DP」的判据 |
| 42 DP 实战 | 动态规划实现 | 搜索引擎拼写纠错（编辑距离） |
引发思考：
- 贪心、回溯、分治、动态规划，四个思想各自的「适用场景」和「能否得最优解」？
- 「最优子结构 + 无后效性」为什么是 DP 的敲门砖？举一个不满足的例子。
- 双十一凑单，为什么不能用贪心（每次选最大可用券），而要用 DP？
9. 模块九：综合应用（第 43–51 讲）
| 讲次 | 核心知识点 | 课程原案例 |
|---|---|---|
| 43 拓扑排序 | 有向无环图的依赖排序 | 确定代码源文件的编译依赖顺序 |
| 44 最短路径 | Dijkstra 算法 | 地图软件算最优出行路径 |
| 45 位图 | 位图 + 布隆过滤器 | 网页爬虫 URL 去重（亿级 URL 内存爆炸） |
| 46 概率统计 | 朴素贝叶斯 | 垃圾短信过滤（概率分类） |
| 47 向量空间 | 向量相似度 | 简单音乐推荐系统 |
| 48 B+ 树 | MySQL 索引底层 = B+ 树 | 从「查询 + 区间查询」需求一步步推导出 B+ 树 |
| 49 A* 搜索 | 启发式搜索 | 游戏中的寻路（估价值引导） |
| 50 索引 | 海量数据索引设计 | 索引结构选型（跳表/B+树/倒排） |
| 51 并行算法 | 并行分治 | 用并行提高算法执行效率 |
引发思考：
- 第 48 讲是「金讲」：为什么 MySQL 索引用 B+ 树，而不是散列表、二叉树、跳表？（从「范围查询 + 磁盘 IO 次数 + 稳定」三个角度，还原课程里的推导过程）
- 布隆过滤器为什么能「用一点点内存判重」，代价是什么？（误判率）——和阶段四 Redis 联动。
- 地图导航用 Dijkstra，游戏寻路用 A*，两者差在哪？（启发函数）
10. 模块十：算法实战（第 52–56 讲，全课升华）
这 5 讲是「把前面学的知识，用来拆解真实系统的底层」——也是这门课的真正价值所在。
| 讲次 | 拆解的系统 | 用到哪些数据结构 |
|---|---|---|
| 52 实战（一） | Redis 常用数据类型 | String→SDS、Hash→哈希表、List→双向链表/压缩列表、ZSet→跳表 |
| 53 实战（二） | 搜索引擎 | 倒排索引、Trie、跳表、B+ 树、AC 自动机 |
| 54 实战（三） | 高性能队列 Disruptor | 环形数组（RingBuffer）、无锁并发 |
| 55 实战（四） | 微服务鉴权 + 限流 | 位图/布隆过滤器（token）、令牌桶/滑动窗口（限流） |
| 56 实战（五） | 短网址系统 | 哈希算法（进制转换）、散列表（存储映射） |
引发思考：
- 学完这 5 讲，你能不能用一句话回答：「Redis 快、搜索引擎快、Disruptor 快，背后的数据结构分别是哪几个？」
- 短网址系统的核心是什么？（把长 URL 映射成短码 = 哈希 + 进制转换，再查表还原）
- 学完整门课，回头再看阶段四《Redis》和《Elasticsearch》，你是不是能「看到」它们底层的数据结构了？
11. 学完这门课，你要能回答的 5 个终极问题
- 什么是复杂度分析？为什么它是「算法学习的精髓」？
- 从数组到 B+ 树，画出这些数据结构的「增删改查复杂度对比表」。
- Redis 的 Sorted Set、MySQL 的索引、搜索引擎的倒排索引，底层各用了什么结构？为什么？
- 贪心、分治、回溯、动态规划，四个思想的核心区别和适用边界。
- 给定一个业务需求（如「实现一个排行榜」「实现一个短网址」），你能独立选型数据结构并说明理由吗？
阅读顺序提示：这门课是阶段三的「第一课 + 主线」，建议用 2~3 个月精读，配合手写实现（数组、链表、栈、队列、树、图、快排、二分）和刷题（第 62–68 讲「春节 7 天练」就是配套练习）。
—— 这是「细化版」学习指南的样板格式。其余课程可按同样深度逐一生成。