霍夫曼编码与计算复杂性
一、固定长度编码不是最优这一篇对应官方 Lecture 38 & 39(Compression & Complexity)。 要把一段文字存成二进制,最直接的办法是给每个字符分配固定长度的编码。8 位能覆盖 256 个字符,够用。 但「够用」和「最优」是两回事。英文字母里,e 出现的频率大约是 z...
基数排序:LSD 与 MSD
一、值域太大怎么办这一篇对应官方 Lecture 35(Radix Sorts)。 计数排序的速度来自一个交换:不做比较,直接用一个计数器数组统计每个取值出现多少次。 但它有一个硬限制:计数器数组的长度必须等于值域大小。键是 0..999 时,开 1000 个格子就够;键是 32 位整数时,值域是 42 亿——开...
比较排序的下界
一、还能不能更快这一篇对应官方 Lecture 34(Sorting and Algorithmic Bounds)。 已经见过 O(N log N) 的排序,也见过退化到 O(N²) 的排序。自然会问:能不能做到 O(N)? 在回答之前,得先把问题拆成两半: 下界不是关于某个算法的结论,而是关于「允许使用哪...
快速排序与三路切分
一、分治的成败全在切分这一篇对应官方 Lecture 30 & 32(Quick Sort)。 快速排序的骨架和归并排序几乎一样:分区、递归。区别是归并排序在合并时干活,快速排序在切分时干活。 切分做的是这样一件事:选一个轴元素,把数组重新排布成「左边都小于轴、右边都大于轴」,然后返回轴最终落到的位置。之...
基础排序:选择、插入与归并
一、一个数字说明不了问题这一篇对应官方 Lecture 29(Basic Sorts)。 「这个排序是 O(N²),那个是 O(N log N)」——这句话在很多场合是对的,但它省略了两件重要的事。 第一件:常数和大 O 是两回事。 N² 和 N log N 在 N 很小的时候可能完全反过来了。实测数据里,N &...
前缀树与自动补全
一、扫描法为什么撑不住前缀检索这一篇对应官方 Lecture 26(Prefix Operations and Tries)。 考虑一个自动补全框。用户敲进两个字母,需要列出词表里所有以这两个字母开头的词。 最直接的做法是扫描整个词表,逐个调用 startsWith: 这个做法的问题不在单次比较有多慢,而在...
最小生成树:Kruskal 与 Prim
一、连通但代价最小这一篇对应官方 Lecture 24(Minimum Spanning Trees)。 一个连通图里的边可能远多于必要的数量。要在所有顶点之间保持连通,需要多少条边? 答案是顶点数减一。一条边最多把两个原本分开的集合合并成一个,从 V 个孤立顶点出发,至少要 V−1 次合并才能连成一体。而恰好 ...
最短路径与 Dijkstra
一、跳数最少不等于距离最短这一篇对应官方 Lecture 23(Shortest Paths)。 在无权图里,一条路径的长度就是它经过的边数,所以「跳数最少」和「长度最短」是同一件事,广度优先搜索一次遍历就能全部算出来。 一旦边带上权重,两件事立刻分家。 实测一张 7 个顶点、10 条边的无向带权图,从顶点 0 ...
图的表示与深度优先、广度优先遍历
一、树和图的唯一差别这一篇对应官方 Lecture 21 & 22(Tree and Graph Traversals & Implementations)。 遍历一棵树之所以简单,是因为有一条性质在保证:从根到任意节点只有一条路径。 所以只要往下走,永远不会回到走过的位置,也不需要担心漏掉谁。 ...
二叉堆与优先队列
一、只要最小元,要不要全局有序这一篇对应官方 Lecture 20(Heaps and PQs)。 假设有一批任务要按优先级调度,每次只取优先级最高的那个。一个很自然的想法是:把所有任务排序,然后从头取。 排序的代价是 N log N,取一个元素是 O(1)。但如果任务在运行中会不断新增,每次新增都要重新排序,或...
哈希表:函数、冲突与装载因子
一、一次查找花在哪一步这一篇对应官方 Lecture 19(Hashing)。 想在一堆键里找一个键,已知的最快方式是二分查找:每比较一次丢掉一半,代价是 log N 次比较。但它有前提——数据必须有序,而且插入新键要挪动数组。 哈希表换了个思路:不算比较次数,直接算出这个键应该在哪。 如果算得足够均匀,一次定位...
B 树与左倾红黑树
一、树高就是访问次数这一篇对应官方 Lecture 17 & 18(B-Trees & Red-Black Trees)。 先算一笔账。假设要在一百万个键里查找,而树是用节点和指针串起来的: 关键在第三行的来源。如果把键按升序逐个插入一棵普通的二叉搜索树,每个新键都比已有的所有键大,于是它永远...
抽象数据类型与二叉搜索树
一、Set 到底是什么这一篇对应官方 Lecture 16(ADTs, Sets, Maps, BSTs)。 问一个问题:Set 和 ArrayList 有什么区别? 如果回答「Set 不能重复、ArrayList 可以」,这只说对了一半。更准确的说法是:Set 是一个抽象数据类型(ADT),它只规定行为,不规定...
并查集:加权合并与路径压缩
一、动态连通性这一篇对应官方 Lecture 14(Disjoint Sets)。 设想一个网络,节点之间不断建立连接。要求是:无论连接怎么加,随时能回答「A 和 B 现在是否连通」。 朴素做法是每次查询都做一次搜索,但连接一多,每次都要重算。并查集换了一个思路:只维护「谁属于哪个集合」,把连通性变成「是否有同一...
渐进分析:大 O、大 Ω 与大 Θ
一、三种记号各自承诺了什么这一篇对应官方 Lecture 13(Asymptotics I)与 Lecture 15(Asymptotics II)。 先摆出最容易被误用的那句话:大 O 不是最坏情况。 O(N) 的意思只是「开销的增长速度不超过 N 的某个常数倍」。它在描述上界: 一个 Θ(N log N) ...

