简介《算法导论》第四版以PDF电子书形式提供面向计算机专业学生、算法学习者及需要夯实理论基础的研发人员系统讲解算法的设计、分析与实现方法。全书从算法在计算中的角色、插入排序与运行时间刻画讲起逐步展开分治与递归式求解、概率分析与随机算法、排序与顺序统计、数据结构、图算法、动态规划、贪心算法、NP完全性及近似算法等核心主题并配有习题与案例分析便于课堂学习、面试复习和科研查阅。压缩包共1个PDF文件大小约19.64MB单文件即包含完整教材内容适合在电脑或平板上阅读与检索。目前已有1247人学习下载可作为长期查阅的算法基础参考书。1. 从伪代码到能跑的代码这本教材真正难啃的地方在哪我见过不止一个人把《算法导论 第四版》的电子版从头翻到尾画了满屏荧光笔关掉阅读器打开编辑器写一个归并排序还是卡在边界的正负一上。这本书的价值从来不在于「读完」而在于把它当成一份写得极严谨、但故意用 1 起始数组和抽象机器模型的规格说明书逐条翻译成本机可执行的代码再用计时和对拍去验证书里的结论。适合读它的是想补算法地基的后端或客户端工程师、做性能优化需要判断复杂度代价的人、以及要从「背过」走到「能推」的人。下面按转写、分析、实现、避坑、验证的顺序把这条路径拆开讲。2. 把伪代码转成 Python1 起始下标、哨兵和递归边界的处理刚上手时最容易低估的就是转写这一步。伪代码看着像 Python实际处处是坑下标基准不同、循环上界是闭区间、哨兵值用抽象符号表示、递归参数是「子数组」而不是切片。这一章把这些差异逐条落到代码上。2.1 书里的数组为什么从 1 开始书里伪代码默认A[1..n]好处是堆的父子关系写成i/2、2i、2i1三个公式长得对称推导时不容易错。换成 0 起始父节点变(i-1)//2左右孩子变2i1、2i2公式立刻变得不对称红黑树和堆的旋转代码读起来也更容易看花眼。转写有两条路选哪条取决于你的目的策略做法优点代价保留 1 起始a [None] data与伪代码逐行对齐便于对照浪费一个槽位切片要写a[1:]全改 0 起始重推所有下标公式符合 Python 习惯能直接进产品堆、树、图的下标要全部重算我的选择是学习期保留 1 起始只为了能拿着书一行一行对写进项目代码时一律 0 起始因为占位元素在后续传参、切片、序列化时会持续制造麻烦。这不是风格问题是两类代码的目标不同一个求「对得上」一个求「不出错」。# a[0] 是占位元素真实数据在 a[1..n] def insertion_sort(a): 对应书里的 INSERTION-SORT(A)下标从 1 开始 n len(a) - 1 for j in range(2, n 1): # 对应 for j 2 to A.length key a[j] # 取出待插入的那张牌 i j - 1 while i 0 and a[i] key: # i 0 就是书里的 i 0别改成 0 a[i 1] a[i] # 比 key 大的整体右移一格 i - 1 a[i 1] key # 空位落 key return a逻辑说明外层从第 2 个元素起内层把比key大的元素逐格右移最后把key放进腾出来的位置。参数上a[0]必须是占位值n由len(a) - 1得到不要拿len(a)当n否则第一次就下标越界。注意内层条件是i 0而不是i 0因为a[0]不参与比较这一点在 1 起始版本里是硬约束。2.2 归并排序的递归边界与切片陷阱书里的MERGE-SORT(A, p, r)传的是下标区间不是子数组。很多人第一反应是写成left merge_sort(a[:mid])、right merge_sort(a[mid:])再拼回去读起来漂亮跑起来很惨每层递归都复制一次数组总复制量 O(n log n)而且全是 Python 层的对象操作。在 n 到十万量级时这段代码比内置排序慢一个数量级以上容易被误判成「归并排序就是慢」。正确的转写是保留lo/hi闭区间只在合并时复制两段数据INF float(inf) def merge(a, lo, mid, hi): # 复制左右两段各在末尾垫一个哨兵省掉每次判空 left a[lo:mid 1] [INF] right a[mid 1:hi 1] [INF] i j 0 for k in range(lo, hi 1): if left[i] right[j]: # 用 而不是 保证稳定排序 a[k] left[i] i 1 else: a[k] right[j] j 1 def merge_sort(a, loNone, hiNone): if lo is None: lo, hi 0, len(a) - 1 if lo hi: # 单元素区间就是递归出口 return mid (lo hi) // 2 merge_sort(a, lo, mid) merge_sort(a, mid 1, hi) merge(a, lo, mid, hi)参数说明lo/hi是闭区间mid (lo hi) // 2向下取整左半段是[lo, mid]、右半段是[mid1, hi]这两个边界写错一个就是死循环或者漏元素。哨兵用float(inf)在纯整数场景会引入浮点比较更稳的做法是取max(a[lo:hi1]) 1或者干脆在merge里加i len(left)的判空——判空带来的分支开销现代 CPU 的分支预测基本能吃下去不必为了省一个判断把哨兵写死。顺带说一个「玄学」现象同一份归并排序代码在近乎有序的数据上并不会比插入排序快因为归并的比较次数始终是 O(n log n)而插入排序在有序输入下退化成一次线性扫描。这不是实现 bug是算法本身的适应性问题别花时间去调常数因子。2.3 哨兵值与抽象符号的替换清单伪代码里那几个符号是转写出错的高发区逐个对上书中写法Python 对应注意事项A[n1] ∞float(inf)或max1哨兵必须严格大于所有可能输入不是「足够大」NILNone链表、树节点判空要显式写is None别用if nodeheap-size(A)单独的size变量不能用len(a)出堆时逻辑堆在收缩、物理长度没变A[1..n]a [None] data取原数组要写a[1:]a[:]多一个占位heap-size那条尤其值得单独拎出来。堆排序的循环是「把堆顶换到末尾heap-size减一再堆化」书里用heap-size(A)表示参与堆化的有效范围。如果直接拿len(a)当边界堆化会把已经排好序的尾部又拖回来参与结果要么顺序错乱要么无限循环。做法很简单函数签名加一个size参数堆化里所有判断都用它。3. 复杂度分析的落地从逐行计数到主定理失效的边界读这本书最容易产生「我懂了」的错觉的地方就是复杂度分析。文字都看得懂换个递归式就不会算。破解办法只有一个把分析过程变成可执行的计数和可拟合的数据。3.1 用逐行计数给插入排序算一遍书里分析插入排序的做法是给每行标代价再对执行次数求和。把这张表原样抄下来你会立刻发现成本主要来自内层的while行代码单次代价执行次数1for j 2 to nc1n2key A[j]c2n-13i j-1c3n-14while i 0 and A[i] keyc4Σtj5A[i1] A[i]c5Σ(tj-1)6i i-1c6Σ(tj-1)7A[i1] keyc7n-1其中tj是第 j 轮内层实际比较次数。最好情况输入已有序tj 1总和化成(c1c2c3c4c7)n - ...是 n 的线性函数最坏情况逆序tj jΣtj n(n1)/2 - 1二次项系数是(c4c5c6)/2。这就是为什么插入排序在「近乎有序」的数据上快得离谱而在逆序数据上慢得离谱——不是常数因子问题是增长阶在变。把这张表变成可实测的东西只要加几个计数器def insertion_sort_counted(a): n len(a) - 1 counts {outer: 0, inner: 0} for j in range(2, n 1): counts[outer] 1 key a[j] i j - 1 while i 0 and a[i] key: counts[inner] 1 a[i 1] a[i] i - 1 a[i 1] key return counts # 随机排列下inner 的期望值约为 n(n-1)/4 import random a [None] [random.random() for _ in range(2000)] c insertion_sort_counted(a) print(c[inner], 2000 * 1999 / 4)逻辑说明counts[inner]统计的就是Σ(tj-1)等于原始数组的逆序对数。随机排列的期望逆序对数是n(n-1)/4实测值围绕它波动偏差在个位数百分比内。这个「跑一遍数一数」的习惯比反复看书有用得多因为它把抽象的 Θ 记号变成了你能打印出来的数字。3.2 主定理什么时候不能套主定理的形式是T(n) aT(n/b) f(n)比较f(n)和n^(log_b a)的大小分三种情形。背下来不难难的是知道它什么时候不适用情形条件结果1f(n) O(n^(log_b a - ε))ε 0Θ(n^(log_b a))2f(n) Θ(n^(log_b a))Θ(n^(log_b a) · log n)3f(n) Ω(n^(log_b a ε))且满足正则条件Θ(f(n))三个常见的失效场景一是子问题规模不相等比如T(n) T(n/3) T(2n/3) n主定理完全用不上得画递归树答案是Θ(n log n)。二是f(n)恰好卡在中间、只差一个对数因子。典型例子T(n) 2T(n/2) n / log n此时n^(log_b a) nf(n)比它小一个log n但又不是多项式级别地小三种情形一种都不满足。直接套会得出Θ(n log n)而正确结果是Θ(n log log n)。三是a或b不是常数比如按√n分治的递归式需要做变量替换n 2^m把式子化简后再用。判断流程我一般这么走先算n^(log_b a)再算f(n) / n^(log_b a)的极限行为。这个比值如果趋向 0、常数、或者某个负幂次三种情形对应得清清楚楚如果比值本身带log因子且既不趋 0 也不发散就老老实实换方法——递归树、代入法、或者 Akra-Bazzi。别硬套硬套出来的答案错得毫无痕迹。3.3 用增长斜率验证而不是相信纸面结论理论算完一遍最好再拿实测数据对一次。做法是取一组等比增长的规模分别计时再对(log n, log T)做最小二乘拟合斜率就是经验增长阶import time, math, random def bench(fn, sizes, repeat5): points [] for n in sizes: data [random.random() for _ in range(n)] best float(inf) for _ in range(repeat): a data[:] t0 time.perf_counter() fn(a) best min(best, time.perf_counter() - t0) # 取最小值压掉调度抖动 points.append((n, best)) return points def fit_slope(points): xs [math.log(n) for n, _ in points] ys [math.log(t) for _, t in points] mx, my sum(xs) / len(xs), sum(ys) / len(ys) num sum((x - mx) * (y - my) for x, y in zip(xs, ys)) den sum((x - mx) ** 2 for x in xs) return num / den参数说明sizes取等比数列比如[1000, 2000, 4000, 8000, 16000]等比才能让 log-log 图上的点均匀分布。repeat取 5 次并取最小值是因为 GC、系统调度、CPU 降频只会让耗时变长最小值最接近真实代价。一个血泪经验别对n 1000的数据拟合。这个区间里常数项和解释器开销占主导斜率会明显偏小很容易得出「这是线性算法」的错误结论。真正的增长阶往往要在n上一个数量级之后才露出来。拟合完对照理论值如果差得远先怀疑测试代码而不是理论——十有八九是基准测试里混进了重复计算或者提前返回。4. 三个核心数据结构的最小实现哈希表、并查集与红黑树书里数据结构的章节篇幅很大但真正在工程里天天用到的就那么几个。挑三个动手写一遍比读三遍有用开放寻址哈希表理解装填因子、并查集理解摊还、红黑树插入理解平衡维护。4.1 开放寻址哈希表装填因子与探测序列链地址法的实现几乎是直白的开放寻址法才有值得琢磨的地方。核心矛盾是删除不能直接把槽位置空否则探测链断裂后面原本能查到的键会查不到。书里给的解法是墓碑标记。class OpenAddressingMap: _DELETED object() # 墓碑删除标记与 None空槽语义不同 def __init__(self, cap8): self.cap cap self.size 0 self.keys [None] * cap self.vals [None] * cap def _probe(self, key, i): # 双重散列h1 i*h2。h2 与 cap 互质才能遍历整张表 h1 hash(key) % self.cap h2 1 (hash(key) % (self.cap - 1)) return (h1 i * h2) % self.cap def put(self, key, val): if (self.size 1) / self.cap 0.7: # 装填因子 0.7 触发扩容 self._resize(self.cap * 2) i 0 while True: idx self._probe(key, i) k self.keys[idx] if k is None or k is self._DELETED or k key: if k is None: self.size 1 self.keys[idx] key self.vals[idx] val return i 1逻辑说明put在遇到空槽、墓碑或同键时停止空槽加计数、墓碑不加它本来就占着位置。_probe用双重散列代替书里演示用的线性探测因为线性探测在高装填因子下会形成长连续段探测长度期望急剧恶化。参数上最要紧的是「h2与cap互质」。容量取 2 的幂时h2取奇数就等价于互质容量取素数时h2取任意小于cap的正整数都行。这一条写错探测序列会在表的某个子集里循环永远碰不到空槽表现为put死循环——排查起来非常费时间因为打印出来的探测下标看着「有规律」。装填因子 0.7 是个经验值再往上探测长度会非线性上涨往下调又浪费空间。4.2 并查集路径压缩加按秩合并并查集是这本书里「理论漂亮且工程真用得上」的典型代表。只做路径压缩是摊还 O(log n)再加按秩合并就是 O(α(n))反阿克曼函数在 n 小于 10^600 时不超过 4工程上直接当常数看。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): # 迭代式路径压缩避免深链递归爆栈 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: # 第二趟把路径上的节点全部挂到根 self.parent[x], x root, self.parent[x] return root def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False # 已在同一集合可用于判环 if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra # 矮树挂到高树下 if self.rank[ra] self.rank[rb]: self.rank[ra] 1 # 只有等高合并才增加秩 return True逻辑说明find用两趟迭代——第一趟找根第二趟压缩这样不会因为递归深度在极端数据上崩掉。union里秩只在两棵树等高时才加一这个细节写错会导致树高增长比预期快性能测试能看出来但不容易定位。rank换成size按节点数合并效果几乎一样实践里我更常用size因为它顺便能回答「这个集合有多大」这类问题而增长率仍然是 O(α(n))。4.3 红黑树插入修复的三种情形红黑树是全书最容易被跳过的一节跳过的人往往也觉得「反正工程里用不到」。确实很少手写但插入修复那三种情形的分类逻辑非常值得过一遍脑——它是「把复杂情况归约成已经解决的情况」的经典套路写业务状态机时经常能借用。插入的新节点染红只可能破坏两条性质根必须是黑、红节点不能有红孩子。修复循环的终止条件就是父节点为黑。核心看叔叔节点的颜色def insert_fixup(t, z): while z.parent is not None and z.parent.color RED: p z.parent g p.parent if p is g.left: y g.right # 叔叔节点 if y is not None and y.color RED: # 情形 1叔叔红。父与叔染黑、祖父染红问题上移两层 p.color BLACK y.color BLACK g.color RED z g else: if z is p.right: # 情形 2三角关系。对父左旋转成一字关系 z p left_rotate(t, z) p z.parent g p.parent # 情形 3一字关系。父染黑、祖父染红对祖父右旋 p.color BLACK g.color RED right_rotate(t, g) else: # 左右对称代码镜像别漏 ... t.root.color BLACK逻辑说明情形 1 只做变色不做旋转把问题上移两层后继续循环情形 2 通过一次旋转把「三角」摆成「一字」代价是循环变量要跟着更新情形 3 旋转加变色之后红黑性质已经全部恢复循环自然退出。最容易被忽略的是最后一行t.root.color BLACK——插入第一个节点时父节点为空循环根本不进根颜色靠这一句兜底。还有对称分支手写时漏掉一边是高频翻车点写完拿区间[1, n]顺序插入加随机插入各跑一遍检查每条路径黑高是否一致比肉眼审查靠谱。5. 避坑转写这本书最容易翻车的五个地方下面五条都是我自己或者身边人真实踩过的按「现象、原因、解决」写方便你对照排查。5.1 转写阶段的三处硬伤坑一堆排序用len(a)当堆大小。现象是排序结果尾部顺序对、头部错乱或者循环退不出来。原因是书里的heap-size(A)是随排序收缩的逻辑边界而len(a)是物理长度始终不变堆化时把已排好的尾部又拖回了堆里。解决办法是把size作为显式参数一路传下去堆化里所有边界判断都用它函数内部不要再出现len(a)。坑二开放寻址哈希表删除时直接置None。现象是删掉一个键之后另一个原本能查到的键查不到了。原因是探测链在空槽处终止删除留下的空洞把链截断了。解决办法是引入墓碑标记查找时跳过墓碑继续探测、插入时可复用墓碑槽位、扩容时统一清理。这条在书里有讲但很多人实现时图省事就略过了等到出问题已经很难回溯。坑三归并排序用切片返回新列表。现象是 n 到十万量级时比内置排序慢十倍以上内存占用也跟着涨。原因是每层递归都复制一遍数组总复制量 O(n log n)而且全是解释器层的对象操作常数极大。解决办法是改成lo/hi原地排序加一次预分配缓冲区合并时只复制待合并的两段而不是整个数组。5.2 分析与设计层面的两处误用坑四主定理硬套带对数因子的递归式。现象是算出来的复杂度和实测斜率对不上差一个log log n量级。原因是f(n)与n^(log_b a)之间只差一个对数因子时三种情形一种都不满足硬套会落到情形 2 上。解决办法是先算比值f(n) / n^(log_b a)看它是不是多项式级别地偏离 1卡在边界上就画递归树或者换代入法别在主定理上赌。坑五把摊还复杂度当成最坏复杂度。现象是按摊还 O(1) 设计的接口在线上偶发超时监控上看平均值一切正常。原因是摊还分析给的是操作序列总代价的上界单次操作最坏可以到 O(n)比如动态数组扩容那一次。解决办法是把这条路径的最坏情况单独拎出来测 p99 和 p999必要时加容量预留或者分批扩容别只看平均数。6. 把书读成自测题随机对拍与 DP 表格的验证技巧读到图算法和动态规划这两部分光看懂已经不够了——这两类算法的错误往往不体现在小样例上而是藏在特定结构里。我习惯用两种手段自查。6.1 用随机对拍验证最短路思路很简单拿一个「肯定对但慢」的实现当基准随机生成输入比对结果。非负权图用 Dijkstra 对 Bellman-FordDijkstra 用堆优化版本Bellman-Ford 的 O(VE) 在几十个节点的图上完全够用。import heapq def dijkstra(n, adj, s): dist [float(inf)] * n dist[s] 0 pq [(0, s)] while pq: d, u heapq.heappop(pq) if d dist[u]: # 惰性删除过期条目直接跳过 continue for v, w in adj[u]: if d w dist[v]: dist[v] d w heapq.heappush(pq, (dist[v], v)) return dist def bellman_ford(n, edges, s): dist [float(inf)] * n dist[s] 0 for _ in range(n - 1): # 最多 n-1 轮松弛 changed False for u, v, w in edges: if dist[u] w dist[v]: dist[v] dist[u] w changed True if not changed: # 提前收敛省掉剩余轮次 break return dist参数说明adj是邻接表adj[u] [(v, w), ...]edges是三元组列表。对拍时随机生成n在 5 到 60 之间、边数在n到3n之间的非负权图跑一百组只要有一组距离数组不一致就打印出来单独看。这套方法抓过我好几次错有一次是 Dijkstra 的松弛条件写成了d w dist[v]非负权下也能出结果但对拍立刻暴露。还有一次是图里存在重边时取最小权的那步漏了单看代码完全看不出来。6.2 动态规划的表格自检DP 的错基本集中在三处边界初始化、转移方向、状态定义。我的检查方法是把表打出来人工验三个点。以最长公共子序列为例表dp[i][j]表示前缀长度第 0 行第 0 列必须全 0转移只看左上、上、左三个格子最终答案在右下角。打印出来后依次确认第一行第一列是不是全零每个格子的值是不是不超过min(i, j)从右下角回溯出来的路径长度是不是等于答案。三条都对实现基本没问题。再补一条经验DP 的状态定义一旦用文字写不清楚代码一定写不对。我现在的习惯是先在注释里用一句话把dp[i][j]的含义写死写完再动手返工率能降一大半。最后说个我自己的教训。早些年读这本书总想着「先把理论过一遍用的时候再回来查」结果每次回来查都要重新理解一遍符号体系等于读了三次。后来改成每读完一节就立刻写可执行版本加一个对拍脚本进度慢了但留在手上的东西是真的。如果你也在啃这本书别追求翻完页数追求「这一节的代码我能不看书写出来并验证」。希望帮到你。本文还有配套的精品资源点击获取