Book Notes · CLRS · Proofs & Bounds

算法导论
超纲分界

按基础 / 排序与顺序统计 / 数据结构 / 高级设计分析 / 图算法五块读。408 只需薄层；摊还与红黑证明细节标「进阶 / 超纲」。

01基础

渐进记号、分治递归、循环不变式。大 O 是上界，不是精确步数；平均必须带分布前提。

问题→分治→主定理 / 展开

归并、快排、折半是大纲内的分治实例。主定理的三种情况点到「怎么套」即可，不要把证明全过程默进统考。

堆排序、快排、线性时间排序、选择问题。建堆 O(n)。快排在输入等概率/随机枢轴假设下平均 O(n log n)，最坏 Θ(n²)。

比较排序最坏下界 Ω(n log n) 是决策树论证，408 点到即可。计数排序要求关键字可映射到有限整数区间；基数排序要求关键字可按位/域分解，且每一趟必须稳定。

稳定：直接插入、冒泡（相等不换）、归并稳定。堆排与默认快排通常不稳。不要写「插入家族都稳定」。

基本结构、散列、BST、B 树。单链表定位 O(n)，改链要前驱。BST 是 O(h)。B 树：根若非叶至少 2 叉，非根内部结点至少 ⌈m/2⌉ 叉，单结点根可为叶。B+ 记录只在叶，分隔关键字可上层重复。

散列最坏 O(n)。本站二次探查约定 h+i²。

进阶 / 超纲红黑树五条性质的插入/删除修复证明、扩充数据结构（顺序统计树）的维护不变量，统考不要求展开。AVL 旋转保 h=Θ(log n) 即可。

进阶 / 超纲动态规划整章、包含活动选择在内的一般贪心证明、摊还分析（聚合、核算法、势能）不是 408 数据结构必答。

大纲内能留下的句子：哈夫曼、Dijkstra、Kruskal 是贪心实例，用它们自己的界，不要写「贪心都是 O(n log n)」。DP 在数据结构科目不单列。

BFS/DFS、最小生成树、单源最短路、全源最短路。邻接表 O(V+E)。Dijkstra 边权非负。Floyd 允许负权禁负环。

Bellman-Ford 标准单源版本只能检出从源点可达的负权环。拓扑只对 DAG。

进阶 / 超纲差分约束、Johnson 算法、最大流与匹配，不要带进 408 数据结构答题。

不要当必答。记「近似平衡、查找对数」即可。插入修复的全部情形标超纲。

不能。摊还分析不借助概率分布，把任意操作序列的总成本分摊到各次操作；单次最坏仍可很高，摊还界不能替代单次最坏界。它也不是「平均复杂度」。

不矛盾。演示图全非负，Dijkstra 适用。有负权换 Bellman-Ford 或 Floyd，并记住 BF 只检源点可达的负环。