企业官网建设流程全解析

简介：《算法导论》第四版英文原版PDF，面向计算机科学与软件工程专业的学生、算法面试备考者及需要系统夯实算法基础的研究人员，用于解决算法设计与复杂度分析缺乏权威系统教材的问题。资源包共1个PDF文件，约19.64MB，为MIT Press 2022年出版的完整电子书，含目录、前言、各章正文、参考文献与索引，篇幅完整，便于全文检索与打印。全书依次覆盖算法在计算中的角色、插入排序与算法分析、渐近记号与运行时间刻画、分治与递归式求解、堆排序、快速排序、线性时间排序、中位数与顺序统计、哈希表与二叉搜索树、红黑树与B树、图算法、动态规划、贪心算法、摊还分析、最短路径、最大流、线性规划、FFT、数论算法、字符串匹配、计算几何、NP完全性及近似算法，并配有大量习题与思考题，可配合课程逐章研读或用于面试前查漏补缺。目前已有1247人学习下载。

1. 拿到《算法导论》第四版 PDF 先别翻第一页：目录里藏着三条不同的读法

《算法导论 第四版 PDF》在硬盘里放了三个月、真正翻过的只有前四十页，这事儿在职工程师里很常见。2022 这一版是 8 个部分、35 章正文加 A 到 D 四个数学附录，正文里列了 231 张插图、931 道练习、162 道章末问题，从第 1 页顺着读到第 35 章，对上班的人来说基本不现实。它真正好用的姿势是当工具书：带着一个具体问题，按目录定位到某一节的伪代码和复杂度推导，看完就用，用完就合。适合三类人——面试前要补渐近分析和图算法的、课程设计里要手写排序/DP/最短路的、工程上要给某个方案找一个严谨上界依据的。这一版相对第三版动了目录骨架，拿旧笔记的章节号直接翻会错位两章，所以先讲地图，再讲怎么落地。

2. 章节地图重排：8 个部分 35 章，按三条路线各取所需

任何一本上千页的教材，目录本身就是一份索引设计。这一版的 8 个部分划分得相当干净：I Foundations（1–5 章）打地基，II Sorting and Order Statistics（6–9 章）讲排序和下界，III Data Structures（10–13 章）是基础结构，IV Advanced Design and Analysis Techniques（14–16 章）讲 DP、贪心、摊还，V Advanced Data Structures（17–19 章）是扩张结构、B 树、并查集，VI Graph Algorithms（20–25 章）覆盖图算法，VII Selected Topics（26–35 章）是选题，VIII 是四个数学附录。部分之间的耦合度比想象中低，作者在前言里也明说了每章相对自足，这就是它能被拆成多条路线的前提。

2.1 三条路线：面试补课、课程设计、工程查表

不同诉求对应的章节集合差别很大，硬按顺序读会浪费大量时间在暂时用不上的内容上。下面这张表是我按实际使用频次整理出来的，投入时间是按每天两小时、边读边写代码估的粗账：

面试路线之所以把 34 章 NP 完全也放进去，是因为“这个问题是不是 NP 难的”经常被当成开放性讨论题，而第 34 章给出的多项式时间归约框架，是唯一能把这类问题答得不含糊的参考。课程设计路线里 24、25 两章值得连着看：24 章的最大流是工具，25 章的二分图匹配、稳定婚姻、匈牙利算法是应用，25.1 明确说了二分图最大匹配可以规约到最大流，两章一起读能省掉一次重复建图的心智负担。

工程路线里最容易被低估的是第 18 章 B 树和第 19 章并查集。前者是文件系统和数据库索引页分裂、合并操作的原始出处，后者在连通性判断、Kruskal 里反复出现。这两章都不长，但用的时候想不起细节会很难受。

2.2 依赖断点：哪几章跳了，后面一定断

有些章可以跳，有些跳了后面就是天书。我踩过的最典型一次是跳过第 4 章直接看第 14 章的矩阵链乘法，那个 DP 转移方程本身不难，但作者在分析里用主定理和递归树去推 O(n³) 的空间、时间界，没有第 4 章的底子就只能干瞪眼。下面四条是我认为的硬依赖：

1. 第 3 章渐近记号加第 4 章主定理，是全书的分析语法。后面每一章都在用 Θ、O、Ω 说话，主定理则是所有分治类递归的判决器。
2. 第 10、11 章是第 17–19 章的前置。17 章的区间树建立在红黑树上，19 章的并查集分析用到摊还，第 16 章不看就直接看 19.4 会卡在势能函数上。
3. 第 20.1 节的图表示决定后面所有图算法的复杂度写法。同一个 Dijkstra，邻接矩阵实现是 O(V²)，换成邻接表加二叉堆才是 O((V+E)lg V)。选错表示，后面所有上界都对不上。
4. 第 34 章先于第 35 章。近似算法的“近似比”这个概念，前提是承认精确解在多项式时间内拿不到；不懂 NP 完全，35 章的各种界就是一堆没有动机的不等式。

2.3 星号小节怎么取舍：只影响证明，不影响实现

这一版沿用了用 ★ 标注研究生层次内容的惯例，主要出现在 4.6（连续主定理的证明）、5.4（指示随机变量的进一步应用）、19.4（按秩合并与路径压缩的分析）、31.8（素性测试）、32.3（有限自动机字符串匹配），附录里还有 C.5（二项分布的尾部）。这些小节的特点是：证明更重，但对应的代码实现往往在相邻的非星号小节里已经给全了。

举个具体的，19.3 节给出的并查集森林实现（按秩合并 + 路径压缩）本身不带星号，代码十几行就能写完；19.4 星号节做的是把 m 次操作的摊还代价证到 O(m·α(n))，α 是反阿克曼函数。你要是只想跑通 Kruskal，19.3 够了；要在技术评审上解释“为什么这个优化几乎等价于常数时间”，才需要 19.4。我的习惯是第一遍只读非星号节，把代码跑通、把上界记成结论；第二遍带着问题回来补证明。这样能把一本书拆成两本用，第一本是工程手册，第二本是理论参考。

3. 伪代码落地：1-indexed 下标与三处哨兵的迁移方案

这本书的伪代码有两个鲜明特征：数组下标从 1 开始，以及用 ∞ 或 −∞ 当哨兵来省掉边界判断。这两点在纸面上让代码更干净，但直接抄进 Python、Java、Go 会系统性出错，而且错的方式很隐蔽——不是报错，是结果少一个元素或者顺序微妙的错。这一章把插入排序、归并排序、堆排序、快排分区四段搬下来，每一段都对着书上的循环不变量讲清楚改了什么。

3.1 下标迁移的三种策略与选择

1-indexed 到 0-indexed 有三条路可走，选哪条取决于你当前是在“抄书验证”还是“写生产代码”：

1. 全局加偏移：书上写 A[i]，代码里写 a[i-1]。最贴近原文，但每个下标表达式都要手动减一，循环条件里的 i ≥ 1 要变成 i ≥ 0，改漏一处就是越界或漏元素。
2. 前置哑元：数组第 0 位空着不用，真实数据从下标 1 开始。改动最小，抄书时可以逐行对照，代价是浪费一个槽位、序列化时要跳过它。
3. 重写边界：彻底转成 0 起始，循环不变量重新推一遍。最干净，也最适合落进项目，但推导过程要自己重做。

我在抄书阶段一律用第二种，跑通之后再转第三种。下面这个包装类能把越界访问立刻暴露出来，比默默读到错误值强得多：

class OneBased: """把 0 起始的 list 包成书上那种 1 起始数组，内部 a[0] 是哑元""" def __init__(self, data): self.a = [None] + list(data) # 第 0 位留空，对应书上的 A[0] 不存在 def __getitem__(self, i): if i < 1: # 书上的伪代码永远不会访问 A[0]，访问到就是迁移出错了 raise IndexError(f"1-based 数组不接受下标 {i}") return self.a[i] def __setitem__(self, i, v): if i < 1: raise IndexError(f"1-based 数组不接受下标 {i}") self.a[i] = v def __len__(self): return len(self.a) - 1 def to_list(self): return self.a[1:]

__getitem__里那道i < 1的检查是这段代码唯一的价值所在：它把“下标差一”这个静默 bug 变成了一行异常。to_list()负责在跑完之后剥掉哑元，避免污染下游。参数上没有可调项，data传任何可迭代对象都行，长度不限。真正要注意的是别在性能敏感的地方用它，包装层的开销在百万级元素上会有感知，那时候老老实实做第 3 种迁移。

3.2 插入排序与归并排序：两份能逐行对照书页的实现

第 2.1 节的插入排序是全书第一个完整算法，循环不变量写得极清楚：外层循环每轮开始时，a[0..j-1]是原数组前 j 个元素的一个有序排列。落到 0 起始的 Python 上，唯一的变化是内层循环的终止条件从i > 0变成i >= 0：

def insertion_sort(a): """INSERTION-SORT(A)，对应 2.1 节；原地排序，0 起始下标""" for j in range(1, len(a)): key = a[j] i = j - 1 # 书上是 while i > 0 and A[i] > key，0 起始后改成 i >= 0 while i >= 0 and a[i] > key: a[i + 1] = a[i] i -= 1 a[i + 1] = key return a

key变量是必须的，它是“待插入的当前元素”，不缓存下来会被后续的右移覆盖掉。a[i+1] = key放在循环外面而不是里面，是因为循环结束时i指向第一个不大于 key 的位置，插入点永远在它右边一格。这个算法的时间界书上给的是 Θ(n²)，但最好情况（输入已排好序）是 Θ(n)，因为内层 while 一次都不进。很多人只记住 O(n²) 就下结论说“插入排序没用”，实际上小数组或者近乎有序的数据上它比快排还快，这也是工程实现里在快排递归到长度小于十几时切插入排序的原因。

归并排序的 MERGE 过程更值得说，因为它是哨兵用得最典型的地方。书上的做法是在左右两个子数组末尾各放一个 ∞，这样主循环里就不需要判断“某一边是否已经取完”：

INF = float("inf") def merge(a, p, q, r): """MERGE(A, p, q, r)，对应 2.3 节；区间语义为 a[p..q] 与 a[q+1..r]""" left = a[p:q + 1] + [INF] # 书本的 L[n1+1] = ∞ right = a[q + 1:r + 1] + [INF] # 书本的 R[n2+1] = ∞ i = j = 0 for k in range(p, r + 1): if left[i] <= right[j]: a[k] = left[i] i += 1 else: a[k] = right[j] j += 1 def merge_sort(a, p=0, r=None): """MERGE-SORT(A, p, r)，自顶向下分治""" if r is None: r = len(a) - 1 if p < r: q = (p + r) // 2 merge_sort(a, p, q) merge_sort(a, q + 1, r) merge(a, p, q, r) return a

p、q、r三个参数是闭区间语义，q属于左半段、q+1属于右半段，这一点跟书上一模一样，不要改成半开区间，否则merge里的切片和主循环范围会同时错位。INF用浮点无穷大是图省事，如果数组里可能出现 inf 或者要做整数类型的严格比较，换成math.inf同上，更稳妥的写法是真哨兵不参与比较、改成显式的剩余元素搬运。

哨兵带来的收益是主循环里少一次条件判断，代价是循环次数比实际元素多（最后会各取一次哨兵）。所以 MERGE 的循环次数是 n1 + n2，正好等于 r − p + 1，不会多跑。这一点在书上 2.3 节的分析里写得很细，值得对照着看一遍，因为它解释了为什么加了哨兵之后复杂度界没有变。

3.3 堆排序与 PARTITION：下标算错一位就是死循环或漏元素

堆排序是全书里下标最容易写错的一段。书上用 1 起始，父节点是 ⌊i/2⌋，左孩子 2i，右孩子 2i+1；换成 0 起始后，父节点是 (i−1)//2，左孩子 2i+1，右孩子 2i+2。这个映射关系只要错一个，堆性质就维护不住，表现出来是排序结果“大致有序但局部乱”，很难查。

def max_heapify(a, i, size): """MAX-HEAPIFY(A, i)，对应 6.2 节；size 是当前堆的有效长度，不是数组长度""" l = 2 * i + 1 r = 2 * i + 2 largest = i if l < size and a[l] > a[largest]: largest = l if r < size and a[r] > a[largest]: largest = r if largest != i: a[i], a[largest] = a[largest], a[i] max_heapify(a, largest, size) # 只递归被交换下去的那棵子树 def build_max_heap(a): """BUILD-MAX-HEAP(A)，对应 6.3 节；从最后一个非叶节点倒着下沉""" for i in range(len(a) // 2 - 1, -1, -1): max_heapify(a, i, len(a)) def heapsort(a): """HEAPSORT(A)，对应 6.4 节""" build_max_heap(a) for end in range(len(a) - 1, 0, -1): a[0], a[end] = a[end], a[0] # 堆顶最大值换到已排序区前端 max_heapify(a, 0, end) # 注意传 end，把已排好的尾巴排除在堆外 return a

max_heapify的第三个参数size是这段代码的关键，也是最常被写成len(a)的地方。排好序的部分在数组尾部，如果不把它排除在堆的有效长度之外，刚换下去的最大值会被重新上浮回堆顶，整个循环就退化成死循环或者结果全错。build_max_heap的起点len(a)//2 - 1是最后一个非叶节点，书上给的是 ⌊n/2⌋，1 起始下的最后一个非叶节点，转到 0 起始正好差一。

快排的 PARTITION 是另一处高发区。书上 7.1 节的写法是i = p − 1，j从p到r − 1，最后把主元A[r]换到i + 1的位置：

def partition(a, p, r): """PARTITION(A, p, r)，对应 7.1 节；以 a[r] 为主元，返回其最终位置""" x = a[r] i = p - 1 # 小于等于主元的区间是 a[p..i] for j in range(p, r): if a[j] <= x: i += 1 a[i], a[j] = a[j], a[i] a[i + 1], a[r] = a[r], a[i + 1] return i + 1 def quicksort(a, p=0, r=None): if r is None: r = len(a) - 1 if p < r: q = partition(a, p, r) quicksort(a, p, q - 1) quicksort(a, q + 1, r) return a

i的初值必须是p − 1，写成p会漏掉第一个元素参与比较的机会，而且当a[p]本身小于主元时会发生元素自己跟自己交换，结果看着对但某些输入下会丢元素。<=和<的选择会影响重复元素的分布：用<=时等于主元的元素全被划到左边，遇到全相同数组会退化成 O(n²)；7.3 节给的随机化版本就是拿这个没办法的办法，工程里更常见的是三路划分，书上的习题里有。

4. 复杂度分析写成代码：主定理判定、Akra-Bazzi 求 p 与摊还代价实测

第 4 章和第 16 章是很多人读这本书时唯一会卡住的地方，不是因为难，而是因为书上给了方法却没给“怎么验算”。理论部分的结论都能手推，但手推容易自我说服，把情形 2 和情形 3 用混。这一章把主定理的判定过程写成可执行的脚本，再用动态表的摊还分析做一次实测校准，让结论能对上数。

4.1 主定理三种情形写成代码：谁和 n^log_b a 比

第 4.5 节的主定理处理的是 T(n) = a·T(n/b) + f(n) 这种形式，a ≥ 1、b > 1。判定核心是拿 f(n) 和临界函数 n^(log_b a) 比大小，三种情形分别是：f 多项式级别地小（情形 1，解是 Θ(n^(log_b a))）、同阶（情形 2，多一个 log 因子）、多项式级别地大且满足正则条件（情形 3，解是 Θ(f(n))）。纸面上看很直白，但“多项式级别”这四个字是判定的关键，也是手推时最容易糊弄过去的地方。

import sympy as sp n = sp.symbols("n", positive=True) def classify(a, b, f): """按 4.5 节判定 T(n) = a*T(n/b) + f(n) 落在哪种情形。 a: 子问题个数；b: 规模缩小倍数；f: 分解与合并的代价表达式 返回 (情形描述, 解的阶) """ p = sp.log(a) / sp.log(b) # 临界指数 log_b a critical = n ** p ratio = sp.simplify(f / critical) # f 与临界函数的比值 # 用 log_n(ratio) 的极限判断 ratio 是否是“多项式级别”的大小 growth = sp.limit(sp.log(ratio) / sp.log(n), n, sp.oo) if growth.is_number and growth < 0: return "情形1", critical if growth.is_number and growth > 0: # 情形3 还需要正则条件：存在 c<1 使 a*f(n/b) <= c*f(n) return "情形3（需验证正则条件）", f if growth == 0: # ratio 是 log n 的幂次，指数 k 决定多出来的 log 因子 k = sp.limit(sp.log(ratio) / <p> <a href="https://download.csdn.net/download/weixin_44015486/88243389" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>