简介《算法导论》英文原版教材PDF面向计算机专业学生、考研备考者以及需要夯实算法基础的开发者提供从基础概念到算法设计的系统学习材料。内容取自Thomas H. Cormen等四位作者合著的第三版原书按Foundations、Sorting and Order Statistics、Data Structures等部分展开涵盖插入排序与算法分析、渐近记号与增长函数、分治法与递归式求解、概率分析与随机化算法、堆排序与快速排序、线性时间排序、哈希表与二叉搜索树以及动态规划、贪心算法、回溯法等经典方法并配有伪代码与习题。压缩包内仅有1个PDF文件体积约5.12MB这个PDF文件就是完整教材便于在电脑、平板或电纸书上离线阅读和检索也方便按章节打印并做笔记。目前已有640人学习适合配合课程进度精读也可长期保存作为查阅算法模板与证明思路的手册。1. 《算法导论》是什么一本被当成字典翻的算法教材很多人第一次听到“算法导论”这四个字会以为它是一本教人写代码的书。真拿到手才发现它更像一本字典厚、全、条目清晰很少有人从头读到尾而是在某个具体问题上翻到对应那一页。这份英文原版第三版把算法的家底摊得很开——排序、哈希表、二叉搜索树、动态规划、图算法、线性规划、NP 完全性34 章加上数学附录凡是计算机里反复被用到的解法基本都能在里面找到出处。搞懂它的价值不在于背下哪段代码而在于建立一套判断标准面对同一个问题怎么看出哪种做法更快、为什么快、快在哪里、代价又是什么。这套标准才是它在课程之外还被人反复翻阅的原因。2. 算法到底是什么一份能被机器照着做的菜谱“算法”这个词在面试、课程和技术文章里出现的频率极高但真要让人用一句话说清它和“一段代码”的差别很多人会卡住。这一章就从这个最基础的困惑入手把算法这件事拆开看。2.1 从一次理牌说起算法是步骤不是代码想象你在打牌左手是已经理好顺序的牌右手不断摸新牌。每摸一张你会从右往左比一遍找到它该待的位置插进去左边那叠牌始终保持有序。这个动作你做过无数次快到不用思考但它其实是一套完整、确定、有限步内必然结束的流程——这就是插入排序。书里讲插入排序时先给的是英文描述加伪代码而不是某种语言的实现。把它翻译成 Python大概长这样# 插入排序把列表当成手里的牌逐张插到左边已经排好序的部分 def insertion_sort(a): for i in range(1, len(a)): # 第一张牌天然有序从第二张开始 key a[i] # 当前摸到的这张牌 j i - 1 while j 0 and a[j] key: # 左边比它大的牌统统右移一位 a[j 1] a[j] j - 1 a[j 1] key # 空出来的坑位放这张牌 return a参数只有一个待排序的列表a函数直接在原列表上操作不需要额外申请一块同样大的空间。key保存当前要插入的值j是向左扫描的指针。注意内层while的两个条件j 0防止扫出边界a[j] key决定什么时候停。这段代码最坏情况下要把每个元素都和前面所有元素比一遍比较次数约是 n²/2但如果输入的列表本来就有序内层循环一次都不会进只需要 n 次比较。同一段代码两种输入下的表现差出一个数量级——这正是“分析算法”这件事存在的理由光看代码看不出快慢得看它在什么输入上做什么事。2.2 为什么它坚持用伪代码而不是某门语言翻几页就会发现这本书几乎不绑定任何编程语言。它用英文句子加一段自成一体的伪代码来描述算法下标、循环、交换、递归这些基本动作都有约定俗成的写法。这么做有个很实际的好处伪代码把“怎么做”和“用什么写”彻底分开了。一旦落到具体语言麻烦事就来了。Python 的列表切片会复制、C 的数组越界不会报错、Java 的整数有溢出边界、某些语言的对象分配有额外开销。这些细节对工程师很重要但对理解算法本身是噪音。伪代码只保留逻辑骨架读者自己翻译成顺手的语言时只需要关心两件事数据结构怎么映射边界条件怎么处理。提示把伪代码翻成真实代码时最容易翻车的不是循环体而是下标起点和空输入。书里默认数组下标从 1 开始很多语言从 0 开始逐行照抄时容易整体偏移一位。这种写法也解释了为什么这本书能同时服务三类人上课的学生照着伪代码理解思路工程师照着伪代码落地实现做研究的人照着章节末尾的注释去追原始文献。同一套描述三种用法。2.3 循环不变式怎么说明一个算法“真的对”写出一段能跑的代码不难难的是说清它为什么在任何输入下都对。书里反复用的是一个叫“循环不变式”的工具思路跟数学归纳法很像在循环开始前找一个始终成立的性质证明每次循环都保持它循环结束时这个性质恰好等价于“答案正确”。拿插入排序走一遍。不变式可以这样定外层循环每轮开始时a[0..i-1]这一段是排好序的而且恰好是原来那前 i 个元素。初始化i 等于 1 时这一段只有a[0]一个元素单个元素天然有序成立。保持假设第 i 轮开始前成立本轮把a[i]插进前面的有序段插入过程只是把比它大的元素依次右移不改变元素集合插完仍然有序于是第 i1 轮开始前也成立。终止循环跑完时 i 等于 n整个数组有序。三步走完正确性就有了着落。这套方法的价值在于它比“我拿几组数据试了试都没问题”可靠得多——跑通几组数据只能说明这几组没翻车说明不了第 n1 组会不会出事。书里几乎每个算法都配了这样的论证这也是它读起来比一般教程费劲的原因。2.4 算法为什么被当成一种“技术”书的第一部分专门讨论过一件事算法不只是数学练习它是和硬件并列的一种技术。硬件的进步是普适的换一台更快的机器所有程序都跟着快一点算法的进步是定向的同一个问题换一种解法可能直接从“跑不完”变成“秒出结果”。输入规模 nn² 级别的运算次数n log₂n 级别的运算次数1,000约 100 万约 1 万1,000,000约 1 万亿约 2000 万这张表说明的问题很直白数据量小的时候两种做法的差距还能靠机器性能糊过去数据量一大差距就变成了“能不能做完”的区别。硬件提升几个百分点要花一代产品的周期而把 O(n²) 换成 O(n log n)往往只是一次思路调整。注意增长阶的对比只在 n 足够大时才有指导意义。n 只有几十的时候一个常数因子很小的 O(n²) 实现完全可能跑赢一个常数因子很大的 O(n log n) 实现。这一点在后面讲复杂度误区时还会再提。3. 复杂度与增长函数大 O 记号为什么成了通用语言如果只记住这本书里的一个符号大多数人会选大 O。它在技术文档、面试对话、开源项目的说明里无处不在但真正能把它说准的人并不多。这一章从“为什么不直接掐表”开始把增长函数和几个渐进记号讲清楚。3.1 为什么不直接掐表增长函数的用处衡量一段代码快不快最直觉的办法是跑一遍看耗时。这个办法在真实工程里当然要用但它有三个绕不过去的毛病。第一耗时依赖机器。同一段代码在笔记本上跑 0.8 秒在服务器上跑 0.2 秒你说它到底是快还是慢第二耗时依赖输入。排序一万个已经有序的数和一万个逆序的数耗时差出好几倍报哪个数字第三耗时依赖实现细节。同样是快速排序用递归写和用手写栈写常数因子能差一截。增长函数换了个问法不问“跑多久”而问“当输入规模翻倍时工作量大概涨多少倍”。这样一来机器、语言、编译器这些变量都被排除在外剩下的只有算法本身随规模变化的趋势。线性增长意味着输入翻倍、工作量翻倍平方增长意味着输入翻倍、工作量翻四倍指数增长意味着输入多一位、工作量翻好几倍。趋势一旦确定就能预测大输入下的表现而不必真去跑一遍。代价也是有的增长函数会把常数因子和低阶项丢掉。2n² 和 100n² 在渐进意义上是同一类可实际跑起来差五十倍。所以书里在给出渐进结果之后往往还会讨论具体操作次数和实现层面的取舍。3.2 O、Ω、Θ三个记号回答三个不同的问题很多人把这三个记号当成“复杂度”的三种写法混着用其实它们各自回答的问题完全不同。记号读法含义回答的问题O(f(n))大 O渐进上界最坏情况下不会比这更慢Ω(f(n))大 Omega渐进下界最好情况下也不会比这更快Θ(f(n))大 Theta渐进紧确界上下界同阶就是这么多用插入排序举例最坏情况是 Θ(n²)最好情况是 Θ(n)所以笼统地说它“是 O(n²)”没错但信息量很少说它“最坏 Θ(n²)、最好 Θ(n)”才把话说全了。这里有个高频误区口语里说“快速排序是 O(n²)”其实指的是最坏情况说“快速排序是 O(n log n)”指的是平均情况或者期望时间。两句话都对但省略了前提听的人容易误解。写文档时把“最坏”“平均”“期望”这几个限定词补上能省掉很多争论。书里还系统讲了渐进记号的形式化定义用存在常数和某个规模阈值来刻画“足够大以后”。这层定义平时用不上但在读论文、看算法分析证明的时候绕不开。3.3 递归式怎么解代入法、递归树和主定理分治类算法天然带递归运行时间的表达式也是递归的比如归并排序的 T(n) 2T(n/2) Θ(n)——把问题分成两半各自递归再花线性时间合并。怎么从这种式子解出闭式结果书里给了三套工具。代入法是先猜一个答案再用数学归纳法验证。猜得准就很快猜不准就得来回试。递归树是把递归展开画成一棵树每层的代价加起来树的深度决定总规模这个方法直观适合找直觉。主定理则是给一类标准形状的递归式直接套公式T(n) aT(n/b) f(n)比较 f(n) 和 n 的 log_b(a) 次方这两个量谁大就归谁管一样大就乘上一个 log 因子。归并排序代进去a2、b2、f(n)Θ(n)而 n 的 log₂2 次方正好是 n两者同阶属于主定理的第二种情况结果是 Θ(n log n)。二分查找代进去a1、b2、f(n)Θ(1)n 的 log₂1 次方是 1同样同阶结果多出一个 logΘ(log n)。注意主定理只覆盖标准形状遇到 T(n) 2T(n/2) n log n 这种夹在两种情形之间的公式套不进去得回到递归树或者代入法。书上为此专门留了一节讨论主定理的证明和边界。这三套工具的关系可以理解成螺丝刀、扳手和电动起子日常大多数情况电动起子最省事碰到特殊规格还是得手动上。3.4 摊还分析偶尔很慢为什么整体还是快有一种情况会让复杂度分析显得很矛盾某个操作绝大多数时候只要 O(1)但偶尔一次要花 O(n)。那它到底算快还是慢书里用一个很贴切的例子来说明——动态表。一个能自动扩容的数组平时插入一个元素就是放到末尾代价 O(1)可一旦容量满了就得申请一块更大的空间、把老元素全搬过去这一次代价 O(n)。如果只看最坏的单次操作结论是 O(n)听起来很糟。摊还分析换了个算法不盯单次盯一串操作的总代价再平摊到每次。容量按倍数增长时扩容发生在第 1、2、4、8、16……次插入总的搬运次数是 124…n约等于 2n平摊到 n 次插入上每次仍然是常数。书里给了三种分析手法聚合分析直接算总账记账法给每个操作预存一点“额度”势能法把预存的额度写成一个势函数。三种手法结论一致只是切入角度不同。这套思路在工程里非常有用。缓冲区扩容、哈希表rehash、并查集的路径压缩都属于“偶尔一次很贵、整体很便宜”的结构用摊还的眼光看才不会被单次最坏情况吓住。4. 设计方法的分水岭分治、动态规划、贪心到底差在哪学算法到一定阶段会发现真正难的不是记住某个具体算法而是面对一个新问题时判断该往哪个方向想。书里把设计技术单独成篇恰恰是因为这个判断比具体实现更值钱。这一章把三种最常用的思路摆在一起对照。4.1 分治切开、递归、合并分治的套路非常固定把原问题拆成若干个规模更小的同类子问题分别递归求解再把子问题的答案合并成原问题的答案。三个动作——分解、解决、合并——缺一不可。书里用最大子数组问题做引子。给定一个可能含负数的数组找出一段连续区间使区间和最大。暴力枚举所有区间是 Θ(n²) 甚至 Θ(n³)而分治的做法是把数组从中点切成左右两半最大子数组要么完全在左半边要么完全在右半边要么横跨中点。前两种递归求解第三种从中点向两侧各扫一遍求最大后缀和与最大前缀和线性时间搞定。整体是 Θ(n log n)。归并排序是同一个骨架拆成两半、各自排好、线性合并。二分查找也算每次砍掉一半只递归其中一边递归式从 2T(n/2) 变成 T(n/2)复杂度从 n log n 降到 log n。这个差别说明分治的效率很大程度取决于“子问题有几个、规模减到多少”。分治能不能用关键看两点子问题是不是相互独立合并步骤能不能高效完成。子问题一旦互相重叠分治就会开始做重复劳动这就引出下一种方法。4.2 动态规划把算过的答案存进表格动态规划处理的是另一类问题子问题之间有大量重叠直接递归会把同一个子问题算上很多遍。经典的例子是斐波那契数列朴素递归的时间复杂度是指数级的因为它把 f(n-1) 和 f(n-2) 里相同的子问题反复重算而把算过的结果存起来复杂度立刻降到线性。书里用钢条切割、矩阵链乘、最长公共子序列这几个问题来展开。以最长公共子序列为例两个序列的最长公共子序列长度可以用一张二维表递推出来# 最长公共子序列dp[i][j] 表示 a 前 i 个字符与 b 前 j 个字符的 LCS 长度 def lcs_length(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表比原串多一行一列专门用来表示“其中一个序列为空”的情况这样循环体里就不用写一堆边界判断。填表顺序是从左上到右下因为每个格子只依赖它左边、上边和左上角的值——依赖方向决定了遍历顺序这是动态规划实现时最容易搞错的地方。动态规划有两个必要前提最优子结构也就是大问题的最优解由子问题的最优解拼成重叠子问题也就是递归过程中同一子问题会被反复求解。缺了第一条子问题的答案拼不出全局最优缺了第二条记忆化就白存了还不如直接用分治。4.3 贪心每一步都拿眼前最好的贪心的思路听起来最不讲道理每一步都选当前看起来最优的那个选完不回头也不保留备选方案。它凭什么对书里用活动选择问题来演示。一堆活动各自有开始和结束时间要选出最多的互不冲突的活动。贪心策略是按结束时间排序每次选结束最早且与已选活动不冲突的那个。这个策略可以严格证明是最优的结束越早给后面留的余地越大。但贪心远不是万能的。最经典的反例是找零钱面值 1、3、4要凑出 6。贪心先拿最大的 4剩 2只能拿两个 1一共三枚而最优解是两个 3只要两枚。贪心在这里给出了次优解原因在于它做了选择之后没有后悔的余地。# 贪心找零面值 1、3、4目标 6会得到 411 共 3 枚 def greedy_coin(coins, target): coins.sort(reverseTrue) # 从大到小挑 count 0 for c in coins: # 每一步都拿当前能拿的最大面值 count target // c target % c return count # 最优解其实是 33共 2 枚这段代码只有六行但它清楚地说明了一件事贪心策略的正确性必须单独证明不能凭直觉。判断依据通常归结为两条——贪心选择性质即存在某个最优解包含当前这次贪心选择最优子结构即做了这次选择之后剩下的问题仍是最优子问题。两条都成立贪心才站得住。书里还讲了 Huffman 编码那是贪心用得最漂亮的地方之一每次合并频率最低的两个节点最终得到的编码长度最优。证明过程用的正是贪心选择性质加最优子结构这套组合拳。4.4 三者的对照什么时候该换招维度分治动态规划贪心子问题关系相互独立大量重叠每次只留一个是否保留备选递归返回后合并表格里保留全部状态选完即定不回头正确性依据合并步骤正确最优子结构 重叠子问题贪心选择性质 最优子结构典型问题归并排序、最大子数组钢条切割、矩阵链乘、LCS活动选择、Huffman 编码常见翻车点子问题其实有重叠白算状态定义漏了维度想当然认为局部最优就是全局最优判断顺序可以这样走先看子问题是否重叠不重叠就分治重叠了看能不能证明贪心选择性质能证就用贪心不能证就老老实实上动态规划。贪心写起来最短、跑起来最快但它对问题的要求也最苛刻证不出来的时候别硬上。5. 常见误区几个一字之差、用起来天差地别的概念学到一定程度卡住人的往往不是某个算法不会写而是几个概念在脑子里搅成了一团。这一章挑五个最容易混的点逐一说清边界。5.1 算法、程序、实现会写代码不等于懂算法易混点把“算法”和“程序”当成同义词觉得写出能跑的代码就算掌握了。为什么容易混日常交流里两个词经常互换着用“这个功能用什么算法实现”和“这段程序怎么写的”听起来问的是同一件事。怎么区分算法是解决问题的步骤描述独立于语言和机器程序是算法在某种环境下的具体实现要处理输入输出、错误、内存、并发这些工程问题。同一个算法可以有几十种实现性能差出好几倍同一段程序也可能混用了好几个算法。书里明确说过它只讲算法的逻辑不涉及错误处理这类依赖具体运行环境的工程细节。5.2 时间复杂度与实际耗时大 O 不是秒表易混点看到 O(n log n) 就以为它一定比 O(n²) 跑得快。为什么容易混既然叫“复杂度”直觉上就该和快慢挂钩。怎么区分渐进复杂度描述的是随规模变化的趋势它故意丢掉了常数因子和低阶项。输入只有一百个元素时一个常数极小的 O(n²) 实现完全可能赢过一个常数很大的 O(n log n) 实现。反过来当 n 涨到百万级趋势就会压过一切常数差异。判断该看哪个取决于你的实际规模在哪个区间。注意算法库的选型经常栽在这上面。小数据集上跑基准测试选出来的“最快实现”换到生产规模可能完全不是同一回事。5.3 动态规划、分治、记忆化搜索三个词经常被混着说易混点把带缓存的递归一律叫动态规划把动态规划一律叫分治。为什么容易混三者在代码形态上确实相似都是“把大问题拆小”。怎么区分分治要求子问题独立不共享结果记忆化搜索是自顶向下的递归加缓存本质是动态规划的一种实现方式动态规划则通常指自底向上填表。真正的分界线不在写法而在子问题是否重叠不重叠就是分治重叠了才轮得到动态规划至于自顶向下还是自底向上只是实现风格的选择。同一个 LCS 问题两种写法都能得到正确答案。5.4 数据结构与算法谁服务于谁易混点觉得这是两门独立的课学完就各自放一边。为什么容易混教材通常分两部分讲名字也不一样。怎么区分数据结构是存放和组织数据的方式算法是操作数据的步骤两者是互相选择的关系——哈希表让查找平均 O(1)但代价是失去顺序二叉搜索树保留顺序代价是最坏情况退化成链。选算法时实际上在选数据结构选数据结构时又在限制算法的空间。书里把数据结构单独成篇紧接着才是图算法和设计技术这个编排本身就说明了依赖关系。5.5 平均情况、最坏情况、期望时间随机化不是碰运气易混点把“平均情况”和“期望时间”当成一回事觉得随机化算法就是赌运气。为什么容易混三个词都带着“大概”的意味中文里又常常一起出现。怎么区分平均情况是对输入分布做假设假设输入是随机的然后算平均表现最坏情况是对任何输入都成立的上界期望时间则是算法内部主动引入随机性之后对随机选择取期望——它不依赖输入分布而是依赖算法自己的随机数。快速排序的随机化版本就是典型即使对手精心构造了最坏输入随机选主元也能让期望时间保持在 O(n log n)。这不是赌运气是把最坏情况的概率压到极低。6. 什么时候该翻这本《算法导论》几个场景和几条提醒说了这么多概念最后落到实际什么情况下值得把这本书打开什么情况下打开它反而是浪费时间。按目的对号入座比较省事你的目的该看的部分预期收获搞清复杂度分析怎么做第一部分基础与附录的求和、概率能自己写出递归式并解出来补数据结构底子第三部分基础数据结构与第五部分知道每种结构的代价和适用边界学设计方法而不是背算法第四部分动态规划、贪心、摊还分析面对新问题能判断该往哪想做图相关的功能第六部分图算法BFS、DFS、最短路、最小生成树、最大流查某个具体算法目录加章节末尾注释拿到伪代码、正确性论证和原始文献线索反过来说有几种情况这本书不是最优选择。想快速上手刷题直接做题、看题解、补基础语法效率更高啃这本厚书容易半途而废想找某门语言的标准库实现去看该语言的文档更直接想在项目里落地一个功能工程上的取舍、依赖、可维护性往往比渐进复杂度更关键。这本书的定位是打地基和做参考不是速查手册也不是实现指南。我自己有过一次挺典型的翻车。当年为了赶一个数据处理的活随手写了个嵌套循环去算两两之间的关系本地拿几百条样本试跑得飞快觉得没问题。上线之后数据量涨到几十万那一晚的等待时间足够我把整个下午重写一遍——两层循环的代价随规模平方增长而换成先排序再扫描的线性做法同样的数据几秒钟就出结果。从那以后我每次动手前都强制走一遍先估输入规模的上限量级写出增长阶再看常数因子能不能接受最后才敲代码。这个习惯比记住任何一个具体算法都管用。这本书的价值也在这里它不会替你做决定但会把每个决定的代价摊开给你看。手上这份英文原版第三版适合放在桌边当参考需要的时候按页面提示取用就行。希望帮到你。本文还有配套的精品资源点击获取