第 02 卷 · 数学基础、数据结构与问题求解
本卷的定位与入口
先修：数学从集合、逻辑、计数与对数讲起；实现练习需要 Go 函数、循环与集合，链表还需要指针。按学习路线，S1 穿插 02.01–02.05，S4 进入树、堆、图及后续算法深化；不把证明、概率与摊还分析压在同一次入门课中。
本卷按起步、原理、工程和进阶分层；首次进入时按阶段学习路线选取当前需要的章节。
已完成的独立章稿
02.01 离散对象与成本模型、02.02 线性结构、02.03 搜索与循环不变量、02.04 哈希与集合、02.05 排序与分治、02.06 树与有序索引、02.07 堆与优先调度、02.08 图与依赖遍历、02.09 加权路径与状态空间、02.10 动态规划与贪心、02.11 近似与专用结构及02.12 业务算法评审已完成。02.01 从 01.01–01.04 的基础进入；后续依次增加指针、线性结构、有序边界、精确身份、排序规则和 S4 有序索引、调度与关系。
02.01 第一遍先读对象、单位、计数、操作模型和增长界；第二遍再深入最坏/平均/摊还、概率、归纳与不变量。02.02 用容量 4 的状态表说明线性结构；02.03 说明二分边界；02.04 区分本地判重和长期幂等；02.05 用并列键说明稳定性与确定性；02.06 用同一会话序号讲树的退化、平衡和多路页树；02.07 从完全树进入堆与有限调度；02.08 用六用户关系和任务依赖区分无向与有向图。02.09 用同一纸图区分最少跳数、最低代价与负权/不可达；02.10 用预算 4 的 0/1 小表对比动态规划与贪心；02.11 用 Trie、位图、Bloom 与并查集解释精确/近似和误判后果；02.12 把输入分布、正确性、基准、内存和退化收束为一页算法评审卡；本卷十二章独立正文已齐。
IM 主线中的位置
历史查找与分页、会话索引、消息去重、发送队列、定时任务和群关系；每种算法先讲数学前置。
主参照与源码入口见 OpenIM 阅读地图。各章区分公开项目事实与虚构教学规则，在具备先修后对照固定源码。
参考材料怎样进入课程
采用经典资料的知识覆盖与递进思路，结合 Go 和虚构 IM 重新组织。下表对应本卷已完成的十二章；按先修选择章节并完成独立变式。
起步层
| 章节 | 要详细讲解的内容 | IM 练习与验收目标 |
|---|---|---|
| 02.01 离散对象与成本模型 | 集合、关系、命题、归纳直觉；计数、对数、概率比例；输入规模与操作次数。 | 用消息数、会话数和设备数计算工作量；先补集合、逻辑、计数与对数再比较成本。 |
| 02.02 线性结构 | 数组、链表、栈、队列、环形缓冲；局部性与容量；操作不变量。 | 设计有限发送队列，比较数组、链表和环形缓冲，解释满队列与出队后的内存保留。 |
| 02.03 搜索与循环不变量 | 线性搜索、二分、上下界；区间约定与终止；重复元素和空输入。 | 在已排序消息序号中找补拉起点，写出区间与循环不变量，处理空历史和重复边界。 |
原理层
| 章节 | 要详细讲解的内容 | IM 练习与验收目标 |
|---|---|---|
| 02.04 哈希与集合 | 哈希函数、冲突、负载因子、扩容；最坏情况；顺序与确定性。 | 为本地消息ID去重设计集合，解释冲突、容量、窗口和不能据此推出的分布式保证。 |
| 02.05 排序与分治 | 比较器、稳定性；插入、归并、快排；时间/空间权衡；外部排序入口。 | 按教学排序规则整理历史消息，说明并列键、稳定性、外部排序及时间戳的局限。 |
| 02.06 树与有序索引 | 二叉搜索树、平衡直觉、遍历；多路树与 B+ 树；范围查询。 | 比较会话内序号范围查询与精确消息查找，画出退化树、平衡树和多路索引。 |
工程层
| 章节 | 要详细讲解的内容 | IM 练习与验收目标 |
|---|---|---|
| 02.07 堆与优先调度 | 堆不变量、上浮下沉、Top-K、延时队列；与排序整个集合的比较。 | 用堆处理有限个到期任务或Top-K热点会话，说明N与K变化时的成本。 |
| 02.08 图与依赖遍历 | 邻接表、BFS/DFS、访问标记、连通性、环与拓扑顺序。 | 用图分析用户关系或处理依赖，解释遍历、访问标记和循环依赖。 |
| 02.09 加权路径与状态空间 | 最短路径、非负权前提、搜索剪枝、可达性与代价。 | 在虚构投递路径图上比较最少跳数与最低代价，构造负权和不可达反例。 |
进阶层
| 章节 | 要详细讲解的内容 | IM 练习与验收目标 |
|---|---|---|
| 02.10 动态规划与贪心 | 子问题、状态、转移、边界、重叠；局部最优的条件与反例。 | 用有限预算选择消息处理批次，定义状态与转移，反驳不满足条件的贪心规则。 |
| 02.11 近似与专用结构 | Trie、位图、Bloom filter、并查集；空间、误判与删除约束。 | 比较历史关键词前缀、位图与去重预筛选；说明Bloom误判不能直接作为丢弃消息依据。 |
| 02.12 业务算法评审 | 输入分布、复杂度、正确性证据、基准、内存与退化策略。 | 提交消息索引或调度算法评审，包含输入分布、正确性、规模、内存与退化方案。 |
本卷综合任务
为消息历史查询和有限发送队列比较数据结构，包含去重、优先处理与容量限制；用手算、性质和规模对照解释选择。
任务由学习者在具备环境时执行。理论推导、参考示例、个人实现和真实运行记录分别保存，故障与反例属于必需部分。
达到的能力
能说明算法为什么正确、什么时候退化、规模扩大后的资源成本；不以刷题数量作为能力证明。
用解释、最小实现、失败变式、业务取舍四类证据评审。只有目录、术语定义或参考代码通过，不能直接记为掌握本卷。
本卷章节展开规则
每章从一个明确问题开始，先补齐本章所需定义，再推导机制；至少含一条完整执行过程、一个反例、分层练习、反馈与业务迁移。复杂章节拆成多课，不把整卷知识压成一次速读。
当前编写状态和章节深度要求见课程编写与能力验收。