数据结构与算法

在度量效率之前，先把三件事定义清楚：什么算一个算法、什么算它是对的、什么算一步操作。本讲给出 RAM 计算模型、循环不变式的三段式证明法，并区分抽象数据类型与数据结构。

渐近记号的精确定义、四种常见误用、增长率层级与数量级直觉、常用求和公式，以及渐近分析在什么情况下会给出错误的工程建议。

分治算法的代价写成递归式后如何求解：代换法（猜与证，含减低阶项技巧）、递归树（先猜后验）、主定理三种情形的完整条件与直觉，以及主定理失效时的处理办法。

当单次操作很贵但很少发生时，最坏情况分析会给出过于悲观的结论。三种摊还分析方法的完整推导：动态数组的倍增、二进制计数器、栈的多重弹出，以及摊还与平均、期望的本质区别。

序列 ADT 的三种实现及其代价矩阵：静态数组、动态数组（Go slice 的增长策略）、单链表与双链表。附哨兵节点技巧、缓存局部性对实测性能的支配作用，以及链表在真实工程中的正确位置。

三种受限序列 ADT 的 Go 实现与应用：栈与括号匹配、表达式求值、显式栈消除递归；环形缓冲队列的容量判定技巧；单调栈与单调队列这两个把 O(n²) 降成 O(n) 的模式。

从直接寻址到散列表：简单均匀散列假设下链地址法的期望代价推导、装填因子的作用、除法法与乘法法的取舍、全域散列的定义与碰撞概率证明，以及散列洪水攻击为什么迫使所有现代语言引入随机化。

开放寻址的三种探查方式与聚簇现象、探查次数 1/(1−α) 的推导、墓碑删除的代价、Robin Hood 与 Cuckoo 散列的最坏保证、一致性散列如何把再平衡代价降到 K/n，以及布隆过滤器的误判率公式与最优参数。

排序问题的两个基准算法：插入排序的精确代价与逆序对的关系、归并排序的分治结构与稳定性、原地与稳定这两个常被忽略的维度，以及用归并统计逆序对这一经典的「分治顺带解决另一个问题」的例子。

二叉堆的数组表示与堆序不变式、sift-down 与 sift-up 的实现、自底向上建堆为什么是 Θ(n) 而非 Θ(n log n) 的完整推导、堆排序、Top-K 与流式中位数的标准解法，以及各类堆的复杂度对照。