简介这是一份由MIT Press出版的经典英文原版教材《算法导论》第四版PDF作者为Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein是计算机科学领域公认的算法权威著作面向计算机专业学生、程序员及算法研究者帮助读者系统掌握算法的设计、分析与实现方法。全书覆盖算法基础、排序与选择、数据结构、图算法、动态规划、贪心算法、回溯算法、分治算法、近似算法以及NP完全理论等核心主题并对时间复杂度与空间复杂度分析方法做了详细讨论包含矩阵乘法等高级专题配有大量习题与实践案例既能用于校园课程学习、考研备考也便于程序员面试复习或日常技术提升。资源包内为1个PDF文件大小约19.64MB方便离线阅读与检索。已有1246人学习下载作为经典教材对深入理解算法、提升编程功底具有很高的参考价值。1. 算法导论第四版PDF先理解它是一本怎样的训练手册算法导论第四版这份PDF是我电脑里存活时间最长的技术资料之一。它不像常见教程那样教你快速调包而是把算法分析这套功夫拆开揉碎从插入排序到红黑树从动态规划到NP完全性每一章都给出伪代码、正确性证明和复杂度推导。这本书解决的核心问题不是“某个算法怎么调用”而是“面对一个陌生问题怎么设计、怎么分析、怎么判断值不值得用”。适合准备算法面试的开发者、需要给学生讲底层设计的老师以及想补性能分析功力的后端和算法工程师。PDF版本的好处是全文可检索、批注不心疼跨章节跳转比翻纸质书顺得多——二刷时你一定会感谢这个格式。2. 上手路线版本差异、全书地图、渐近记号与第一个移植代码2.1 第四版“新”在哪里新增了哪些专题第四版和第三版相比一个最直观的变化是把新方向收了进来新增了机器学习算法整章含聚类、乘性权重算法和梯度下降把经典算法和现代AI之间搭了一座桥在线算法也单独成章讲电梯等待、搜索表维护和在线缓存这类带时间维度的决策问题。对老读者来说更明显的变化是插图换成双色印刷图例清晰很多部分内容做了重写和拆分比如匹配问题扩展成了一章。我的实际体感是这一版更适合当工具书常翻常新。目录里从“算法在计算中的角色”一路铺到近似算法内容跨度极大但章节足够自包含。你不必从第1章线性读到第35章完全可以按需进入。这也是为什么很多高校和公司把它当案头手册而不是“必须从头啃完”的教材。2.2 八部分内容地图与两种通读顺序拿到PDF后第一件事是看目录而不是看正文。全书分为八个部分外加数学附录大致可以按下表理解部分章节范围核心内容推荐定位Part I1-5章算法入门、渐近记号、分治、概率分析必读打底Part II6-9章堆排序、快速排序、线性时间排序、选择算法必读面试高发区Part III10-13章数组链表、哈希表、二叉搜索树、红黑树必读工程索引基础Part IV14-16章动态规划、贪心、摊还分析核心方法论Part V17-19章扩充数据结构、B树、不相交集合数据库与并查集考点Part VI20-25章图遍历、最小生成树、最短路、最大流、匹配必读重中之重Part VII26-35章并行、线性规划、FFT、数论、字符串、机器学习、NP完全按需查阅AppendixA-D求和、集合、计数与概率、矩阵随时回查通读顺序上面试导向我建议走这条线Part I → Part II → Part III → 第14章动态规划 → Part VI → 第34章NP完全性与第35章近似算法。研究导向则按原书顺序配合星号章节深入。用我自己带人的经验说第一次通读把主干放在前14章和图算法其余章节先留个印象遇到问题再回来查。这样不会因为某章的数学证明难就卡住整个进度。2.3 渐近记号速查O/Ω/Θ怎么读第三、四章的核心是渐近记号这部分是整本书的语法基础。以下几个记号抓住本质就行记号口语含义判定方式O上界最差不会超过这个量级存在常数c和n₀对所有n≥n₀有f(n)≤c·g(n)Ω下界至少是这个量级存在常数c和n₀对所有n≥n₀有f(n)≥c·g(n)Θ紧致界正好这个量级同时满足O和Ωo非紧上界f(n)/g(n)趋近于0ω非紧下界f(n)/g(n)趋近于无穷看复杂度不要靠玄学就拿循环嵌套和递归式算。迭代算法数循环层数递归算法套主定理。主定理的三种情况值得专门背熟因为很多面试题最终都会收敛到“T(n)2T(n/2)O(n)所以总复杂度是Θ(nlogn)”这类结论。2.4 伪代码到Python的第一个移植插入排序书中第2章用插入排序开篇这是最好的入门移植案例。伪代码数组下标从1开始而Python从0开始移植时统一减一def insertion_sort(a): n len(a) for j in range(1, n): # 对应伪代码 for j 2 to A.length key a[j] i j - 1 while i 0 and a[i] key: a[i 1] a[i] # 右移给key腾位置 i - 1 a[i 1] key # 插入到正确位置 return a arr [5, 2, 4, 6, 1, 3] print(insertion_sort(arr)) # [1, 2, 3, 4, 5, 6]这段代码逻辑说明两点外层range(1, n)对应伪代码中j从2到数组末尾因为Python索引从0开始所以整体偏移一位内层while的判断顺序先检查i0再比较a[i]key防止边界越界。参数上不需要额外传数组长度len(a)在函数内部取排序是原地的直接修改传入列表。这里有个隐藏考点如果比较符号从大于改成大于等于相同元素的相对顺序会被打乱稳定性随之丢失。书里用严格大于是因为稳定排序在许多场景下是刚需。2.5 排序算法对比与选型堆排、快排、归并与线性时间排序排序部分占了Part II整整四章工程上最常用的对比表我整理如下算法最坏平均最好额外空间稳定插入排序O(n²)O(n²)O(n)O(1)稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定快速排序O(n²)O(nlogn)O(nlogn)O(logn)不稳定计数排序O(nk)O(nk)O(nk)O(k)稳定基数排序O(d(nk))O(d(nk))O(d(nk))O(nk)稳定桶排序O(n²)O(nk)O(n)O(nk)取决于桶内排序选型逻辑上数据量很小且近乎有序时插入排序常数极小反而最快元素是有限小整数时计数排序能到线性通用大数据量场景用快排或归并要求最坏有保证且原地时选堆排。语言内置排序大多是混合策略比如小规模转插入排序这也是为什么理论与实践要结合着看。2.6 快排的随机化与顺序统计量两个常用代码模板书中第7章的快排必须吃透。工程上实现快排时随机化主元几乎是标配否则对已排序数组会退化成O(n²)。下面是我常用的Lomuto分区写法import random def quicksort(a, lo, hi): if lo hi: return a # 随机选主元并换到开头避免有序数据导致最坏情况 pivot_idx random.randint(lo, hi) a[lo], a[pivot_idx] a[pivot_idx], a[lo] pivot a[lo] i lo for j in range(lo 1, hi 1): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[lo], a[i] a[i], a[lo] quicksort(a, lo, i - 1) quicksort(a, i 1, hi) return a参数说明lo和hi是闭区间边界初次调用传quicksort(arr, 0, len(arr)-1)。平均复杂度Θ(nlogn)最坏O(n²)。随机化只是让最坏情况概率趋近于0真正要从理论上消除最坏情况得用书中后面提的中位数选择做确定性主元但工程上收益不大。顺序统计量问题找第K小元素和快排只差一个递归分支。随机选择算法的期望是O(n)比排序再取第K个快一个量级def randomized_select(a, lo, hi, k): if lo hi: return a[lo] pivot_idx random.randint(lo, hi) a[lo], a[pivot_idx] a[pivot_idx], a[lo] pivot a[lo] i lo for j in range(lo 1, hi 1): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[lo], a[i] a[i], a[lo] rank i - lo 1 # 主元在当前子数组中排第几 if k rank: return a[i] elif k rank: return randomized_select(a, lo, i - 1, k) else: return randomized_select(a, i 1, hi, k - rank)k的语义是从1开始比如找最小值传k1最大值传klen(a)。这里要注意递归时k-rank的偏移因为进入右半部分后已经跳过了前rank个元素。书里还介绍了一个最坏O(n)的确定性算法思路是“中位数的中位数”但常数因子很大实战中很少有人真的去写。3. 数据结构阅读法哈希表、红黑树、B树与摊还分析3.1 哈希表三种冲突处理方式怎么选第11章哈希表是所有语言内置集合的底层理论基础。三种策略对比很清晰方案核心思路适用场景直接寻址表用全域大小建数组O(1)访问关键字的全域很小时链接法冲突元素挂链表通用场景实现简单开放寻址冲突后探测下一个空位负载因子控制得当、不想用指针哈希函数的设计是这章最容易翻车的地方。书中给的是除法散列和乘法散列前者取k mod m后者先乘小数再取整。工程上判断哈希函数好不好我一般会做一个暴力统计往一个容量为10000的表里塞100000个样例看分布方差和最长冲突链长度。如果最长链超过10这个函数就有问题。负载因子αn/m是性能的关键指标。链接法下α大于1时链表变长查找退化开放寻址必须保证α远小于1否则探测次数急剧上升。很多语言实现会在α超过阈值时触发rehash扩容书中动态表那节讲的就是这个机制。3.2 红黑树性质与插入删除的阅读路径红黑树是第13章的内容也是面试里最容易讲不清的一章。五条性质先背熟节点非红即黑、根是黑、叶子和NIL是黑、红节点的子节点必须黑、从根到每个叶子的黑节点数量相同。读插入和删除时我的记忆锚点是“插入看叔叔删除看兄弟”。插入修复关注父节点的兄弟节点颜色删除修复关注兄弟节点的颜色和子节点情况。书里把每种情况画得很细但本质都是在恢复性质5的黑高度平衡。旋转操作本身不复杂难的是判断该用左旋还是右旋练手时建议亲自画一棵不平衡树走一遍。下面这个函数可以在你写出插入删除后自动检查性质是否合法是我复现红黑树时的常备验证手段def check_red_black(root): # 返回 (是否满足红黑树性质, 当前子树黑高度) if root is None: return True, 1 # 空子树视为黑节点 if root.color R: if root.left and root.left.color R: return False, 0 if root.right and root.right.color R: return False, 0 ok_l, hl check_red_black(root.left) ok_r, hr check_red_black(root.right) if not ok_l or not ok_r or hl ! hr: return False, 0 bh hl (1 if root.color B else 0) return True, bh参数说明root每个节点需要有color属性取值为R或B递归返回值中第二个值是黑高度。这个检查本质是在递归后序位置验证每条路径黑节点数一致如果左右黑高度不同说明性质5被破坏。这章读不下去很正常我第一遍也卡了三天。建议先跳过删除部分插入修复看明白删除等真正用到再回读。3.3 B树磁盘I/O场景下的高度与扇出第18章B树主要回答一个问题为什么数据库索引不用红黑树因为磁盘读取一次的代价比内存访问慢几个数量级树的高度决定了查询需要多少次I/O。B树的节点包含多个关键字一次读取整页数据树高大幅降低。概念参数说明最小度数t除根外每个节点至少有t-1个key最多2t-1个key树高高度≤log_t((n1)/2)t越大树越矮分裂子节点满时裂成两个key上提给父节点合并删除导致节点过少时与兄弟合并这里我提醒一句别急着背B树的插入删除代码先理解分裂和合并的触发条件。t2时就是2-3-4树手动画一遍t3的插入就能体会为什么磁盘页大小决定了t的取值。工程上还要考虑是否把叶子节点串成链表做顺序扫描第四版在B树定义上保留了经典表述但实际数据库实现大多在叶子层做了优化。3.4 摊还分析聚合、核算法、势能法第16章摊还分析是我见过最容易被读者跳过、但又最实用的一章。它解决的是“一系列操作的总代价”问题而不是单次最坏复杂度。三种方法本质是同一件事的不同记账方式。聚合分析把n次操作总代价算出来除以n核算法让“便宜”操作存信用“贵”操作取信用势能法用势能函数Φ(Di)表示数据结构当前状态溢出的代价先“预付”。动态表扩容是标准例子单次append最坏O(n)但n次append的总代价是O(n)均摊O(1)。读这章时的可执行步骤是先认准某个操作的输入规模再猜一个势能函数最后验证Φ(D0)0且终态势能非负。如果第4章递归式还没吃透主定理加上势能法会让你看很多证明都顺畅起来。4. 高级设计与图算法动态规划、贪心与图模型4.1 动态规划从钢条切割到LCS的状态转移方程第14章动态规划是我认为整本书性价比最高的一章。四步走定义状态、写状态转移方程、定初始条件、确定计算顺序。钢条切割帮你理解“最优子结构”矩阵链乘法帮你理解“区间DP”最长公共子序列LCS是最典型的双序列DPdef lcs_len(a, b): m, n len(a), len(b) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]dp表尺寸是(m1)×(n1)多开一行一列是为了让i0或j0时不用特判边界。状态转移逻辑很直白当前字符相等答案从左上角加1不相等取左边和上边的较大值。空间优化是DP的进阶点。LCS的递推只依赖上一行可以用两行数组滚动空间从O(mn)降到O(n)。不过要回溯出具体子序列时还是得保留完整dp表。4.2 贪心算法何时能用何时不能用第15章贪心和第14章DP紧挨着是有原因的。两者都需要最优子结构但贪心还多一条“贪心选择性质”局部最优选择能推导出全局最优解不需要考虑替换。活动选择问题是标准入门题所有活动按结束时间排序每次都选结束最早且与已选活动不冲突的那个。证明方式是“交换论证”——把任意最优解的第一个活动换成贪心选择的那个不破坏可行性也不变差。反面经典例子是0-1背包分数背包可以用贪心按单位重量价值装0-1背包不行因为不能拆开导致局部最优不成立。面试里判断一个题能不能贪心我习惯问自己三个问题有没有最优子结构局部最优会不会影响全局能不能找到反例找不到反例不代表成立但能找到反例一定不成立。霍夫曼编码是另一个必须掌握的贪心案例用最小堆反复合并频率最低的两个节点生成前缀码。它之所以能用贪心是因为“两个最低频字符一定在最深层”这个引理成立。4.3 图算法最小集BFS/DFS、最短路径、MST图算法是面试大头第20到23章需要系统读一遍。我整理的最小集合如下问题算法复杂度使用条件无权最短路BFSO(VE)无权的图有向无环图最短路拓扑排序松弛O(VE)DAG含负权最短路Bellman-FordO(VE)无负权回路非负权最短路DijkstraO(E log V)权重非负全源最短路Floyd-WarshallO(V³)稠密图最小生成树Prim/KruskalO(E log V)无向带权图Dijkstra的堆优化版本直接对应书中的优先队列实现工程代码我会这样写import heapq def dijkstra(graph, start): dist {v: float(inf) for v in graph} dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue # 过期的堆项直接跳过 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist参数说明graph是邻接表节点映射到(邻居,权重)列表pq是优先队列。dist记录当前已知最短距离堆里可能同时存在同一节点的多个历史版本所以弹出后先判断ddist[u]跳过过期项。书里花了不少篇幅证明Dijkstra为什么不能处理负权边——因为已确定最短路的节点可能被负权边再次更新而堆里没有机制处理这种“降级”。面试被追问到这里能说出来就是加分项。4.4 最大流与匹配Ford-Fulkerson、匈牙利、稳定婚姻第24到25章把最大流和匹配放在一起讲。Ford-Fulkerson方法每次找一条增广路径把流量压满直到没有增广路。用BFS找增广路就是Edmonds-Karp算法复杂度O(VE²)。最大流最小割定理告诉你最大流的值等于最小割的容量这个结论在分析网络可靠性时非常有用。二分图最大匹配的经典转换是建一个虚拟源点和虚拟汇点把左侧节点连源点、右侧节点连汇点中间的匹配边容量设1跑一遍最大流就得到最大匹配数。但实际工程里常用匈牙利算法替代常数更小。稳定婚姻问题第一次读会觉得像算法游戏实际上它是Gale-Shapley算法解决的问题是“n个求职者和n个岗位如何两两配对且不存在私奔对”。这个算法的一个反直觉结论是进行求婚的一方得到的匹配结果至少不比对方差。第25章匈牙利算法解决的是带权二分图的最优指派复杂度O(n³)。面试见到“安排任务”“分配资源”这类题先画二分图再套算法比硬想贪心靠谱得多。5. 避坑笔记读算法导论第四版最容易翻车的五个地方5.1 阅读顺序与章节选择的坑坑1按目录从第1章线性读到第35章结果卡死在第4章。现象很多读者从第1章开始逐页翻到第4章主定理证明就看不懂了进度停滞一个月。原因这本书章节不是按难度线性排列的第4章的分治证明用到了附录C的数学工具而附录在全书最后。解决先读第1到3章和附录A、C的基础部分第4章拿到主定理三种情况的结论先走证明部分跳过。等后续用到分治再回头补。坑2把星号章节当必读内容白白消耗大量精力。现象看到标★的节比如连续主定理证明、Akra-Bazzi递归式钻牛角尖死磕好几周。原因星号是为研究生深入设计的本科生和工程向读者完全可以先略过。解决第一遍把星号章节全部跳过第二遍或工作遇到具体问题再按需回查。知识储备够时再看这些内容反而是享受。坑3不读附录结果后面所有概率分析都接不上。现象第5章随机算法、第8章排序下界里的组合证明看一行字要想五分钟。原因概率论基础没建立期望、指示器随机变量、二项分布尾部这些前置概念都在附录C里。解决拿出两天时间专门过附录C计数与概率把期望的线性性质练熟。这部分一旦打通第5章和第8章会顺畅很多。5.2 伪代码移植与练习的坑坑4伪代码下标从1开始直接翻译成Python后越界或漏元素。现象照着第2章写插入排序用range(2, len(a))结果第一个元素永远没进循环或者while循环里用a[i]时i已经等于-1直接抛异常。原因书中数组从1索引开始而Python数组从0开始翻译时没有做整体偏移。解决任何伪代码转真实语言时先标注“1-based还是0-based”循环边界统一减一。写完用书中练习题里的示例数组跑一遍如果结果对不上先查边界。坑5只读不练练习和问题全跳过关上书啥都不会。现象每天读几十页读完全书却连快排都手写不出来。原因把算法书当小说读没有动手复现。书中含有931个练习和162个问题练习检验基本掌握问题往往引入新场景和新结论这部分才是精髓。解决每个章节至少完整实现一个核心伪代码每章从课后problems里挑一题做。算法能力只能靠手写练出来看会的和写出来的差距非常大。6. 这本PDF的进阶用法反向索引、自测清单与交叉批注6.1 反向索引让目录变成解题模板库正向阅读是把每个算法都过一遍反向索引则是先拿具体问题回查目录定位到对应章节去取模板。问题类型回看章节核心模板无序数组第K大第9章randomized_select有序数据高效查找第12、13章二叉搜索树、红黑树区间最值、滑动窗口第6章堆、优先队列字符串匹配第32章KMP、Rabin-Karp最优化决策第14、15章动态规划、贪心任务分配、匹配第24、25章最大流、匈牙利、稳定婚姻用这套方法每次做完一道算法题就把题目归到某个章节下相当于用自己的解题经验给全书做一次二次索引。6.2 自测清单每周选一组练习限时完成我的做法是按章挑一组“最低限度清单”数组排序用快排随机化版本、堆实现优先队列、BST的插入删除、LCS动态规划、Dijkstra堆优化版、二分匹配转最大流。每个模板要求在30分钟内从零写完并通过测试不限时写出来的代码不能算掌握。书后面大量练习题适合当题库用同一道题过一个月再写一遍能明显看出自己进步。6.3 交叉批注把PDF当算法笔记的主干PDF格式最适合做交叉批注。我在第4章主定理页贴上自己推导过的递归式算例在第16章摊还分析页记录动态表扩容的势能函数在第24章最大流页补充二分匹配的建图细节。每一轮重读批注都会增长这本书就从一个柏林知识集合变成我个人的笔记索引。从那以后我每次打开算法导论第四版都强制自己先找到对应章节的伪代码手写一遍再谈复杂度这个习惯让我在算法分析和工程选型上都少走了很多弯路。希望帮到你。本文还有配套的精品资源点击获取