《算法导论》第四版：伪代码到可运行代码与复杂度验证

简介：《算法导论》第四版英文原版电子书由 MIT Press 于 2022 年出版，作者为 Cormen、Leiserson、Rivest 与 Stein，面向计算机专业学生、考研备考者、算法岗求职者以及需要系统补齐算法设计与分析基础的研发人员。全书从算法在计算中的角色讲起，依次覆盖插入排序与运行时间刻画、分治策略与递归式求解（代入法、递归树法、主方法）、概率分析与随机化算法、堆排序与快速排序、线性时间排序、中位数与顺序统计量，并延伸至数据结构、图算法、动态规划、贪心算法、近似算法与 NP 完全理论等专题，各章配有大量习题与案例分析，可用于课堂学习、面试复习与工程问题建模。压缩包内仅 1 个 PDF 文件，约 19.64MB，单文件完整保留全书章节与索引，便于检索、做笔记和跨设备阅读。目前已有 1247 人学习下载，适合希望以权威教材贯通算法基础与进阶内容的读者长期查阅。

1. 从「算法导论 第四版.pdf」到可运行代码：先定一条能复现的读法

很多人把《算法导论 第四版.pdf》当成面试前翻一翻的伪代码合集，看完红黑树和动态规划就关掉，真到要写一个能过压力测试的堆，还是从零搜博客。反直觉的是，这份 PDF 最有价值的用法不是“读懂”，而是当一份可执行规格书：每段伪代码配一个测试桩、一组规模阶梯、一张增长曲线，再用对拍卡住边界。它适合想补算法底子又不想停在纸面的后端、数据、客户端工程师，也适合带新人的技术负责人。下面这套读法只围绕一件事：把「算法导论 第四版.pdf」里的抽象步骤落成能调试、能计时、能复现的代码，先让最小用例跑通，再谈复杂度。

2. 伪代码到 Python 的翻译规则：下标、哨兵和测试桩怎么一次对齐

2.1 书里的伪代码为什么不能直接抄：数组下标、哨兵与全局变量

书里的伪代码为了排版和证明方便，经常默认数组从 1 开始，还会用A[0]放哨兵，循环条件写成i > 0。直接抄进 Python，最常见的翻车是下标整体错一位：该访问第一个元素时访问了第二个，该停的时候没停。更隐蔽的是哨兵值混进数据：排序结果里多出一个负无穷，测试桩却只检查长度，最后上线才发现边界用例全挂。

我一般先做一张“翻译对照表”，把书里的写法逐条映射到 Python 的写法，再动手写函数。表不用很大，但必须覆盖下标、交换、长度和哨兵四类问题。下面这张表是我常用的最小版本：

以插入排序为例，书里的外层循环从 2 开始，内层用i > 0控制。翻译到 Python 时，外层从 1 开始，内层必须写成i >= 0，否则第一个元素永远不会被比较。下面这段代码是我作为“翻译模板”反复用的最小版本：

def insertion_sort(a): # 书里的 A[1..n] 平移到 a[0..n-1] for j in range(1, len(a)): key = a[j] i = j - 1 while i >= 0 and a[i] > key: a[i + 1] = a[i] i -= 1 a[i + 1] = key return a

这段代码的逻辑是：外层j表示当前要插入的元素位置，内层把比key大的元素整体右移一格，最后把key放回空位。参数只有一个可变列表a，函数原地排序并返回同一个列表，方便链式调用。空数组时range(1, 0)不执行，单元素时也不执行，边界是安全的。真正要小心的是内层条件：i >= 0不能写成i > 0，否则a[0]永远不参与比较；a[i] > key不能写成>=，否则重复元素会被反复移动，稳定性被破坏。

哨兵的处理更值得单独说。书里用哨兵是为了减少一次边界判断，但 Python 里多一次i >= 0的判断成本很低，把哨兵塞进数据反而让测试桩变复杂。我的习惯是：如果伪代码用了哨兵，翻译时先去掉哨兵，用显式边界条件跑通，再考虑要不要为了性能加回来。加回来时必须单独写一条测试，检查哨兵没有被当成有效数据输出。全局变量也是同理，书里为了证明方便会把计数器、父子指针放在全局，翻译时一律收进类或闭包，否则多组测试之间会互相污染。

2.2 一套最小翻译模板：循环不变式、边界断言与测试桩

伪代码翻译最容易犯的错，是“看起来跑通了”就往下翻页。我的做法是每翻完一个算法，先写三样东西：循环不变式、边界断言、测试桩。循环不变式不用写成形式化证明，用一句大白话写清楚“每一轮开始时，哪段区间已经有序、哪个变量代表什么”。边界断言放在函数入口和出口，入口检查输入类型和长度，出口检查排序性、堆性质或图的可达性。测试桩负责把空数组、单元素、重复值、负数、已排序、逆序这六类用例固定下来。

下面这套模板可以直接抄，插入排序只是示例，换成归并、快排、堆调整都一样：

import random def insertion_sort(a): for j in range(1, len(a)): key = a[j] i = j - 1 while i >= 0 and a[i] > key: a[i + 1] = a[i] i -= 1 a[i + 1] = key return a def is_sorted(a): return all(a[i] <= a[i + 1] for i in range(len(a) - 1)) cases = [[], [1], [2, 1], [3, 1, 3, 2], [-5, 0, -5, 9]] for data in cases: out = insertion_sort(data[:]) assert is_sorted(out), data assert out == sorted(data), data for n in [10, 50, 200]: for seed in range(30): random.seed(seed) data = [random.randint(-100, 100) for _ in range(n)] out = insertion_sort(data[:]) assert out == sorted(data)

逻辑说明：cases覆盖固定边界，随机循环覆盖规模变化；每次传入data[:]是为了保留原数组，失败时能打印输入。参数说明：n是规模起点，seed是随机种子，range(30)表示每个规模跑 30 组。种子必须固定，否则失败用例无法复现。比较时用out == sorted(data)而不是只检查相邻有序，因为相邻有序可能漏掉元素丢失或重复。

提示：测试桩里所有随机数据都固定种子，失败时先复现种子，再缩小规模，不要一上来就打印几千行数组。

循环不变式在这里的用法很具体：插入排序外层每轮开始时，a[0..j-1]已经有序，a[j..]是未处理部分。写测试时就可以针对这个不变量构造用例：已经有序的数组、完全逆序的数组、大量重复值的数组。已经有序时内层不移动，完全逆序时内层移动最多，重复值时检查稳定性。边界断言不用写得太重，assert is_sorted(out)和assert len(out) == len(data)两条就够挡住大多数低级错误。

2.3 参数怎么设：输入规模、随机种子与递归深度

翻译阶段的参数不在多，在于每次只动一个。规模从 10 开始，按 10、50、200、1000 翻倍，观察运行时间和比较次数是否按预期增长。随机种子固定 0 到 29，失败时先定位种子，再把规模缩到最小可复现。数据分布至少四组：随机、升序、降序、大量重复。递归算法还要单独看递归深度，Python 默认递归限制大约 1000，归并排序和快排在大规模下很容易触发RecursionError。我的处理顺序是：先改迭代，实在改不动再设上限，绝不把上限调到十万了事。

递归深度可以用一行命令先看当前限制：

import sys print(sys.getrecursionlimit())

这行代码只做一件事：打印解释器当前的递归上限。参数说明：没有参数，输出是一个整数。看到这个数之后，不要急着调大，先算一下归并排序的递归深度大约是log2(n)，快排最坏情况是n。如果n是 10000，快排最坏递归深度就是 10000，调大上限只是把崩溃延后，正确做法是把小区间改成插入排序，或者用显式栈模拟递归。测试桩是边界条件的后悔药，递归深度是递归算法的黑匣子，这两个地方多花十分钟，后面少熬一晚上。

3. 复杂度分析落地：用计数器和规模阶梯验证 O(n log n) 不是玄学

3.1 从渐进符号到可测量指标：比较次数、交换次数、峰值内存

渐进符号描述的是增长趋势，不是某台机器上的秒数。工程里要验证一个算法是不是O(n log n)，不能只靠time.time()跑一次，因为计时会被冷启动、GC、CPU 调度干扰。我一般同时采集三类指标：比较次数、交换或赋值次数、峰值内存。比较次数最稳定，和输入规模的关系最接近理论值；交换次数能看出数据分布的影响；峰值内存能挡住“时间换空间”换过头的实现。

以归并排序为例，比较次数大致是n log2 n量级，合并次数是n-1。下面这个计数版本把比较次数和合并次数收进字典，跑完直接返回，不污染全局变量：

def merge_sort_count(a): stats = {"cmp": 0, "merge": 0} def merge(left, right): out = [] i = j = 0 while i < len(left) and j < len(right): stats["cmp"] += 1 if left[i] <= right[j]: out.append(left[i]) i += 1 else: out.append(right[j]) j += 1 out.extend(left[i:]) out.extend(right[j:]) stats["merge"] += 1 return out def sort(x): if len(x) <= 1: return x mid = len(x) // 2 return merge(sort(x[:mid]), sort(x[mid:])) return sort(a), stats

逻辑说明：merge里每比较一次就累加cmp，每完成一次合并就累加merge；sort负责二分递归，长度小于等于 1 直接返回。参数说明：a是待排序列表，返回值是(排序结果, 统计字典)。这个版本会复制子数组，空间复杂度是O(n)，但计数准确，适合做规模阶梯。真正上线时再改成原地归并，计数逻辑保持不变。

峰值内存可以用标准库的tracemalloc采：

import tracemalloc tracemalloc.start() merge_sort_count([3, 1, 2]) current, peak = tracemalloc.get_traced_memory() tracemalloc.stop() print(current, peak)

这段代码输出当前和峰值内存，单位是字节。参数说明：start()开始跟踪，get_traced_memory()返回(current, peak)，stop()结束跟踪。注意要在被测函数调用前启动，调用后立刻取值，否则其他分配会混进来。峰值内存不要求精确到字节，看数量级就够：O(n)和O(n log n)的差距在规模翻倍时会很明显。

3.2 三个必调参数：数据分布、规模阶梯、重复次数

复杂度测试最容易犯的错，是只跑一组随机数据，然后拿一次计时下结论。随机数据下快排接近O(n log n)，已排序数据下如果基准选第一个元素，就会退化成O(n^2)；归并排序对数据分布不敏感，但重复值多的时候比较次数会变化。我的固定做法是四组分布都跑：随机、升序、降序、大量重复。每组规模按 100、200、400、800、1600、3200 翻倍，至少六个点，少了看不出趋势，多了跑得慢。

重复次数取 5 次，记录最小值，不记录平均值。最小值受冷启动和调度影响最小，平均值容易被一次卡顿拉高。每次重复前重新生成数据或复制数据，避免原地排序把已排序结果喂给下一轮。下面这张参数表可以直接贴在测试脚本开头：

规模阶梯不是越大越好。规模太大，单次跑几分钟，调试成本高；规模太小，常数项盖过增长趋势。我的经验是先用 100 到 3200 找到趋势，再对可疑区间加密到 6400 或 12800。如果 3200 已经跑不动，说明实现里有隐藏的O(n^2)，先回去查循环，不要急着换机器。

3.3 画一张增长曲线：用脚本自动跑规模阶梯

把计数和规模阶梯串起来，用一个脚本导出 CSV，后面用表格工具画图就行。下面这段脚本跑归并排序，输出规模、比较次数、合并次数三列：

import csv import random rows = [] for n in [100, 200, 400, 800, 1600, 3200]: random.seed(42) data = [random.random() for _ in range(n)] _, stats = merge_sort_count(data) rows.append((n, stats["cmp"], stats["merge"])) with open("merge_stats.csv", "w", newline="") as f: writer = csv.writer(f) writer.writerow(["n", "cmp", "merge"]) writer.writerows(rows) print(rows)

逻辑说明：random.seed(42)保证每个规模的数据分布一致，merge_sort_count返回统计字典，csv.writer写表头和三列数据。参数说明：n是规模列表，42是固定种子，merge_stats.csv是输出文件名。跑完打开 CSV，用cmp除以n * log2(n)，如果比值在一个小范围内波动，说明增长趋势符合预期；如果比值随n明显上升，说明实现里多了隐藏循环。

真正要看的是曲线斜率，不是某个点的绝对值。比较次数曲线在双对数坐标下应该接近直线，斜率约等于 1 加上一个很小的常数。合并次数应该严格等于n-1，如果不是，说明递归分割写错了。计时曲线会有噪声，但规模翻倍时用时大约翻倍多一点，如果翻四倍，就要怀疑退化。复杂度分析不是玄学，把计数器、规模阶梯、重复次数三件事固定下来，每次改动只动一个参数，结论就能复现。

4. 数据结构与图算法实现顺序：堆、散列表、邻接表的边界条件

4.1 先写不变量再写方法：以最小堆的 sift-down 为例

手写堆最容易错的地方不是push，是pop之后的sift-down。我的习惯是先写不变量：对于数组中每个位置i，如果左孩子2*i+1存在，则a[i] <= a[2*i+1]；如果右孩子存在，则a[i] <= a[2*i+2]。不变量写清楚之后，push就是尾部插入再上浮，pop就是取根、把最后一个元素放到根、再下沉。下面这个最小堆实现只保留核心方法，方便对拍：

class MinHeap: def __init__(self): self.a = [] def push(self, x): self.a.append(x) self._sift_up(len(self.a) - 1) def pop(self): if not self.a: raise IndexError("empty heap") root = self.a[0] last = self.a.pop() if self.a: self.a[0] = last self._sift_down(0) return root def _sift_up(self, i): while i > 0: p = (i - 1) // 2 if self.a[p] <= self.a[i]: break self.a[p], self.a[i] = self.a[i], self.a[p] i = p def _sift_down(self, i): n = len(self.a) while True: left = 2 * i + 1 right = left + 1 small = i if left < n and self.a[left] < self.a[small]: small = left if right < n and self.a[right] < self.a[small]: small = right if small == i: break self.a[i], self.a[small] = self.a[small], self.a[i] i = small

逻辑说明：push在尾部追加后上浮，pop取根后用最后一个元素补根并下沉；_sift_down每轮在父、左、右三个位置里选最小，如果父已经最小就退出。参数说明：没有容量参数，数组动态增长；pop空堆抛IndexError，调用方必须处理。边界条件有三个：空堆、单元素堆、只有左孩子没有右孩子。测试时三个都要覆盖，尤其是pop到最后一个元素时，last和root是同一个值，不能再写回根。

4.2 散列表冲突处理的三个参数：装载因子、探测步长、扩容阈值

散列表的坑集中在扩容和探测。线性探测的实现里，删除不能直接把槽位置空，否则后面的探测链会断；要么用墓碑标记，要么重建。装载因子超过阈值必须扩容，否则探测长度会迅速变长。下面这个最小线性探测表只实现put和get，用来演示三个参数怎么设：

class LinearProbeMap: def __init__(self, cap=8, load_factor=0.66): self.cap = cap self.size = 0 self.load_factor = load_factor self.keys = [None] * cap self.vals = [None] * cap def _hash(self, k): return hash(k) % self.cap def put(self, k, v): if self.size / self.cap >= self.load_factor: self._resize(self.cap * 2) i = self._hash(k) while self.keys[i] is not None and self.keys[i] != k: i = (i + 1) % self.cap if self.keys[i] is None: self.size += 1 self.keys[i] = k self.vals[i] = v def _resize(self, new_cap): old = list(zip(self.keys, self.vals)) self.cap = new_cap self.keys = [None] * new_cap self.vals = [None] * new_cap self.size = 0 for k, v in old: if k is not None: self.put(k, v) def get(self, k, default=None): i = self._hash(k) start = i while self.keys[i] is not None: if self.keys[i] == k: return self.vals[i] i = (i + 1) % self.cap if i == start: break return default

逻辑说明：_hash用取模把哈希值压到容量范围，put先检查装载因子，超过就扩容；探测时遇到空槽或相同键停止。参数说明：cap初始容量 8，load_factor默认 0.66，扩容倍数 2。三个参数要一起看：装载因子太高，探测变长；太低，空间浪费；扩容倍数太小，频繁重建。我的起点是容量 8、装载因子 0.66、扩容 2 倍，跑完 10 万次插入再根据探测长度调整。

4.3 图表示选型：邻接表、邻接矩阵与边列表的取舍

图算法第一步不是写 Dijkstra，是选表示。邻接表适合稀疏图，查邻边快，空间是O(V+E)；邻接矩阵适合稠密图，查边O(1)，空间是O(V^2)；边列表适合只需要遍历所有边的算法，比如最小生成树的前置排序。下面这张表是我选型时用的最小对照：

选型的判断标准很简单：先看边数E和点数V的关系。E接近V^2用矩阵，E远小于V^2用邻接表，只需要按权重排序用边列表。不要为了“通用”同时维护三套表示，转换层写一次就够。邻接表建图时注意节点编号：如果输入从 1 开始，先在读入层统一减 1，算法内部只用 0-based，否则后面每个下标都要补一个-1，迟早漏。

4.4 用对拍脚本卡住手写实现的常见错误

手写堆最怕“看起来能排序”，一上大量push/pop就乱序。对拍是最省事的验证：用标准库的heapq作为参考实现，随机生成操作序列，比较每次pop的结果。下面这段脚本可以直接跑：

import heapq import random for seed in range(50): random.seed(seed) h = MinHeap() ref = [] for _ in range(200): if random.random() < 0.6: x = random.randint(-100, 100) h.push(x) heapq.heappush(ref, x) else: if ref: assert h.pop() == heapq.heappop(ref) while ref: assert h.pop() == heapq.heappop(ref)

逻辑说明：随机决定push还是pop，两个实现同步操作，每次pop比较结果；最后把剩余元素全部弹出再比一遍。参数说明：seed跑 50 组，每组 200 次操作，0.6是插入概率。这个脚本能抓住上浮下沉写反、空堆判断漏掉、重复值比较用<=还是<的问题。对拍失败时先打印seed，再缩小操作次数到 10 次，逐条打印操作序列。

5. 避坑与排查：图算法和动态规划复现时最容易被 PDF 带偏的 5 个现场

5.1 Dijkstra 用普通队列也能跑，但大数据超时

现象：小规模图跑得很快，节点数到几万、边数到几十万时，程序卡住不动，计时从毫秒级跳到分钟级。原因：伪代码里写的是“取出当前距离最小的节点”，直接翻译成遍历列表找最小值，每次松弛都要扫一遍所有节点，复杂度退化成O(V^2)。PDF 的证明默认你用了优先队列，但代码里不会替你补。解决：用标准库的heapq维护(距离, 节点)，弹出时如果距离不等于当前记录就跳过，也就是懒删除。下面这段是修正后的核心循环：

import heapq def dijkstra(graph, src): dist = {u: float("inf") for u in graph} dist[src] = 0 pq = [(0, src)] while pq: d, u = heapq.heappop(pq) if d != dist[u]: continue for v, w in graph[u]: nd = d + w if nd < dist.get(v, float("inf")): dist[v] = nd heapq.heappush(pq, (nd, v)) return dist

参数说明：graph是邻接表，graph[u]里每项是(邻居, 权重)，权重必须非负；src是起点。if d != dist[u]是懒删除的关键，跳过已经被更短路径更新的旧堆项。注意浮点权重不要用等值比较，误差会让这个判断失效，权重尽量用整数，或者加一个很小的容差。

5.2 背包压缩维度后答案偏大，内层循环方向反了

现象：0-1 背包用一维数组写，跑小样例正确，换一组数据答案比标准答案大，而且刚好等于“同一件物品被拿了多次”的结果。原因：一维数组压缩后，内层循环如果从小到大遍历，dp[c-w]可能已经包含了当前物品，等于允许重复拿。PDF 里二维表的递推很清楚，压缩维度时方向是隐含的。解决：0-1 背包内层容量从大到小遍历，完全背包从小到大遍历。下面这段是 0-1 背包的写法：

def knapsack_01(weights, values, cap): dp = [0] * (cap + 1) for w, v in zip(weights, values): for c in range(cap, w - 1, -1): dp[c] = max(dp[c], dp[c - w] + v) return dp[cap]

参数说明：weights和values等长，cap是容量，dp[c]表示容量不超过c时的最大价值。range(cap, w-1, -1)是逆序，保证每件物品只用一次。验证时不要只跑一组，至少跑“一件物品”“容量为 0”“所有物品重量大于容量”“价值为 0”四组边界。

5.3 节点编号从 1 开始，邻接表却用 0 下标

现象：图算法在小图上结果对，换一份输入就找不到路径，打印邻接表发现第一个节点是空的，最后一个节点多了一条边。原因：输入习惯从 1 开始编号，建图时直接写graph[u].append(v)，但数组长度是n，下标只到n-1，节点n被写到范围外，节点0永远空着。解决：读入层统一减 1，算法内部只认 0-based。建图代码里加一行断言：

def build_graph(n, edges): graph = [[] for _ in range(n)] for u, v, w in edges: u -= 1 v -= 1 assert 0 <= u < n and 0 <= v < n graph[u].append((v, w)) return graph

参数说明：n是节点数，edges是(起点, 终点, 权重)列表，函数内部完成 1-based 到 0-based 的转换。断言不能省，它是编号错的后悔药。转换只做一次，后面所有算法都用 0-based，避免“这里减一那里不减”的混乱。

5.4 递归快排在大规模下栈溢出，调高上限只是延后崩溃

现象：快排或归并排序在几万条数据时抛RecursionError，把递归上限调到十万后，程序不报错了，但偶尔直接崩溃或者变慢。原因：快排最坏递归深度是n，归并是log n，调高上限只是让栈继续长，内存和调用开销都上去了。解决：快排小区间改用插入排序，递归只处理较小的一侧，较大的一侧用循环；归并如果递归太深，改成自底向上。先看当前上限：

import sys print(sys.getrecursionlimit())

参数说明：输出是解释器当前允许的最大递归深度，默认通常在 1000 左右。不要直接setrecursionlimit(100000)，先算理论深度：归并log2(n)，快排平均log2(n)、最坏n。如果理论深度接近上限，改迭代；如果只是略超，设一个合理上限并加测试。

5.5 复杂度测试只用已排序数据，得出 O(n) 的假象

现象：给插入排序跑已排序数组，计时几乎是一条平线，于是得出“插入排序接近线性”的结论；换随机数据后慢了一个数量级。原因：数据分布单一，已排序是插入排序的最好情况，不能代表平均和最坏。解决：固定四组数据——随机、升序、降序、大量重复，每组都跑规模阶梯，记录最小值和比较次数。测试脚本里不要只写一个random.shuffle，要把四组分布写成函数，循环调用。看到“线性”结论时先问一句：是不是只测了最好情况。

注意：图算法里不要用浮点权重做等值比较，误差会让松弛条件失效；动态规划里不要只验证最终答案，中间状态表也要抽几行对拍。

6. 用对拍和基准测试把「算法导论 第四版.pdf」里的结论跑成自己的数据

翻到最后一章，我不再急着看新算法，而是把前面写过的实现拉出来做两件事：对拍和基准测试。对拍负责正确性，基准测试负责增长趋势，两件事都做完，才算把「算法导论 第四版.pdf」里的结论跑成了自己的数据。下面这个小脚本是我常用的骨架，左边跑手写实现，右边跑参考实现，同时记录最小用时：

import random import time def bench(fn, data, repeat=5): times = [] for _ in range(repeat): t0 = time.perf_counter() fn(data[:]) times.append(time.perf_counter() - t0) return min(times) def check(fn, ref, sizes): for n in sizes: random.seed(42) data = [random.randint(-1000, 1000) for _ in range(n)] assert fn(data[:]) == ref(data[:]), n

逻辑说明：bench对同一份数据重复跑repeat次，返回最小值，避免调度噪声；check在每个规模上固定种子生成数据

本文还有配套的精品资源，点击获取