第 1 章 算法在计算中的作用 (The Role of Algorithms in Computing)
核心结论
-
算法定义：算法是明确定义的计算过程，接受输入值并产生输出值；正确算法对每个输入实例都能停机并给出正确答案。
-
算法解决的问题类型：排序、最短路径、最长公共子序列、拓扑排序、凸包、FFT 等——共同特征是「候选解众多」+「实际应用价值高」。
-
数据结构的作用：没有一种数据结构能适用于所有目的，掌握多种数据结构的优劣是做算法选择的前提。
-
算法设计技术：分治、动态规划、贪心、摊还分析——比单纯记住具体算法更重要，是解决新问题的工具箱。
-
难解问题 (NP-complete)：旅行商等问题目前无已知高效算法；若能证明问题 NP-complete，应转而设计近似算法（第 35 章）。
-
并行性：单核主频遇到物理瓶颈，多核芯片成为主流；第 27 章介绍多线程算法模型以利用多核。
|
本章主旨
本章是全书的导论，回答三个根本问题：什么是算法、为什么值得研究、算法在计算机技术中的位置。从全书的 35 章看，排序 / 搜索 / 图算法 / 优化问题构成主轴；数据结构（第 10-14 章）与算法范式（分治 / DP / 贪心 / 摊还）构成两条横线。第 34 章 NP 完全性 + 第 35 章近似算法给出对难解问题的应对策略。 |
一、核心概念
本章围绕 6 个核心概念展开：先给出算法与数据结构的形式化定义，再列举典型应用场景，最后讨论算法设计技术、难解问题与并行性作为全书的总览。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
算法 (Algorithm) |
明确定义的计算过程，将输入转换为输出；正确性指对每个输入实例停机并给出正确答案。 |
§1.1；可用英语、程序或硬件描述；伪代码表达最常用。 |
数据结构 (Data Structure) |
存储与组织数据的方式以支持高效的访问与修改；不存在万能结构。 |
§1.4 引入；散列表、二叉搜索树、红黑树等贯穿全书。 |
算法设计技术 (Techniques) |
分治 / 动态规划 / 贪心 / 摊还分析——比具体算法更重要的通用工具。 |
§1.4 概览；分治见第 4 章、DP 见第 15 章、贪心见第 16 章、摊还见第 17 章。 |
难解问题 (Hard Problems) |
NP-complete 问题目前无已知多项式算法；TSP 等是其代表。 |
§1.3 + 第 34 章；若 NP-complete 应转用近似算法（第 35 章）。 |
并行性 (Parallelism) |
多核芯片时代的算法设计；多线程算法模型利用多核。 |
§1.4 + 第 27 章；编程模型 chapter 27 给出形式化框架。 |
算法即技术 (Algorithm as a Technology) |
算法与其他计算机技术（硬件、网络、用户界面）并列，是性能的决定性因素。 |
§1.2 论证；当性能成为瓶颈时，算法改进往往比硬件升级更经济。 |
二、详细笔记
2.1 算法的形式化定义
What：算法是良定义的计算过程：接受输入、产生输出、由一系列计算步骤将输入转换为输出。
Why：形式化定义让我们能讨论「正确性」「效率」「下界」等可分析的属性——脱离具体编程语言和硬件，把算法当作数学对象研究。
How：
| 概念 | 描述 |
|---|---|
输入 (Input) |
来自特定集合的取值（可为集合） |
输出 (Output) |
与输入有特定关系的取值（可为集合） |
正确性 |
对每个输入实例，算法停机并给出正确输出 |
描述形式 |
英语、伪代码、程序、硬件设计皆可，但必须无歧义 |
排序问题的形式化：
-
输入：\(n\) 个数的序列 \(\langle a_1, a_2, \ldots, a_n \rangle\)
-
输出：输入的一个排列 \(\langle a'_1, a'_2, \ldots, a'_n \rangle\)，满足 \(a'_1 \leq a'_2 \leq \cdots \leq a'_n\)
When：当任务能用「输入 → 处理步骤 → 输出」三要素描述时。任何图搜索、规划、强化学习都基于这一抽象。
Example：插入排序、归并排序都解决同一形式化问题，但效率不同（前者 \(\Theta(n^2)\)，后者 \(\Theta(n \lg n)\)）。
2.2 算法解决的问题类型
What：典型算法问题的共同特征是「候选解空间巨大」+「实际应用价值高」。
Why：这些问题是理解算法设计技术的载体；也是后续章节展开的具体目标。
How：典型例子：
-
最短路径：给定道路网（图中边带权），找两点间的最短路径。候选解是所有可能的路径，数目指数级。第 24 章单源最短路径给出 Dijkstra / Bellman-Ford 算法。
-
最长公共子序列 (LCS)：给定两序列 \(X = \langle x_1, \ldots, x_m \rangle\) 与 \(Y = \langle y_1, \ldots, y_n \rangle\)，找最长公共子序列。候选子序列 \(2^m \cdot 2^n\) 种，暴力枚举不可行。第 15 章动态规划给出 \(O(mn)\) 算法。
-
拓扑排序：给定 n 个零件的依赖关系（每个零件可能依赖其他零件），找线性顺序使每个零件先于其使用者。候选解 \(n!\) 种。第 22 章用 DFS 给 \(O(V+E)\) 算法。
-
凸包 (Convex Hull)：给定平面上 n 个点，找包含所有点的最小凸多边形。候选子集 \(2^n\) 个。第 33 章给出 Graham 扫描和 Jarvis 步进两种方法。
-
离散傅里叶变换 (DFT)：把时域采样转为频域系数。朴素 DFT 是 \(O(n^2)\)，第 30 章 FFT 给出 \(O(n \lg n)\)。
When：判断一个新问题是否能用算法解决——检查它是否能形式化为「输入/输出」+「良定义的求解过程」。
Example：基因序列比对 = LCS 变种；导航系统 = 最短路径；编译器指令调度 = 拓扑排序。
2.3 数据结构与算法的关系
What：数据结构是存储和组织数据的方式，使访问和修改更高效。
Why：算法是操作数据的步骤；如果数据结构选择不当，再好的算法也会被低效的数据访问拖累。
How：本书数据结构路线图：
| 章节 | 数据结构 | 典型应用 |
|---|---|---|
第 10 章 |
数组 / 链表 / 栈 / 队列 |
基础容器 |
第 11 章 |
散列表 (Hash Table) |
字典、集合、缓存 |
第 12 章 |
二叉搜索树 (BST) |
有序数据 |
第 13 章 |
红黑树 (Red-Black Tree) |
平衡的有序字典（C++ STL |
第 14 章 |
扩充数据结构 |
区间树、顺序统计树 |
第 18 章 |
B 树 |
数据库 / 文件系统 |
第 19 章 |
斐波那契堆 |
Dijkstra 加速 |
第 20 章 |
van Emde Boas 树 |
整数键字典（latency 优化） |
第 21 章 |
不相交集合森林 |
Union-Find / Kruskal |
When：选择数据结构时考虑「最频繁的操作」是什么（查找？插入？删除？最小/最大？）。
Example：编译器符号表需要按名查找 + 插入 + 删除 → 散列表；需要按声明顺序遍历 → 链表；两者结合是常见模式。
2.4 算法设计技术
What：把解决具体问题的方法抽象为通用模式，能应用于一类问题。
Why：比起记住具体算法，掌握技术能让你设计新算法——遇到未见过的题目时知道从何入手。
How：本书覆盖的四大范式 + 一类高级话题：
-
分治 (Divide-and-Conquer)：把问题分解为独立子问题，递归求解后合并。第 4 章给出归并排序、最大子数组、Strassen 矩阵乘法。
-
动态规划 (Dynamic Programming)：把重叠子问题的解存起来避免重复计算。第 15 章给出钢条切割、LCS、最优二叉搜索树。
-
贪心算法 (Greedy Algorithms)：每步做局部最优选择，期望得到全局最优。第 16 章给出活动选择、Huffman 编码、最小生成树的 Kruskal/Prim。
-
摊还分析 (Amortized Analysis)：平均意义上的复杂度（如动态表扩张平均 \(O(1)\) 插入）。
-
多线程算法 (Multithreaded Algorithms)：第 27 章用动态多线程 (work/span) 模型描述并行。
When：拿到新问题时——是否可分解？是否有最优子结构？是否可用局部最优近似？
Example：归并排序体现分治；钢条切割体现动态规划；Dijkstra 算法中的优先级队列选择体现贪心 + 数据结构。
2.5 难解问题与 NP 完全性
What：NP-complete 是一类问题：目前没有已知的多项式时间算法；但也没有人证明这样的算法不存在。
Why：遇到 NP-complete 问题应避免徒劳追求精确解——转而设计近似算法或启发式方法。
How：
-
P 类：多项式时间可解的问题（如排序、最短路径）。
-
NP 类：多项式时间可验证解的问题（包含 P）。
-
NP-complete 类：NP 中最难的一类——任何一个 NP-complete 问题有多项式算法，则所有 NP 问题都有。
-
典型 NP-complete 问题：旅行商 (TSP)、团问题、3-SAT、子集和、汉密尔顿回路。
证明一个问题 NP-complete 通常用归约：从已知 NP-complete 问题出发，把它变换为目标问题。
When：拿到一个看似困难的问题——先查文献看是否已知 NP-complete；如果是，转向近似算法（第 35 章）或启发式。
Example：送货公司每天要从仓库出发送 n 个地址再回仓库，求最短路线 = TSP（NP-complete）。若每天必须精确最优解则不可行；可用 Christofides 算法等近似算法给「差不多最优」的解。
2.6 并行性与多线程算法
What：现代 CPU 已从提高主频转向多核；算法设计必须考虑并行性以利用多核。
Why：单核主频因功率密度问题遇到物理极限——3 GHz 之后每提升 1 GHz 功耗呈超线性增长。「免费的午餐」结束了。
How：
-
动态多线程模型：第 27 章介绍 work/span 概念。
-
work \(T_1\)：单线程执行总时间。
-
span \(T_\infty\)：关键路径长度（理想并行上限）。
-
并行度 \(T_1 / T_\infty\)。
-
调度定理：在 \(P\) 个处理器上调度时间 ≤ \(T_1 / P + T_\infty\)。
-
-
并行原语：
spawn派生子任务、sync汇合、parallel循环。
When：算法中存在独立的子问题（如分治的递归调用）时容易并行；存在数据依赖时（如动态规划的状态转移）需要更精细的处理。
Example：归并排序的并行版本（P-merge sort）能达到 \(O(\lg n)\) 的 span，对应 \(n / \lg n\) 的并行度。
四、思维导图
mindmap
root((第 1 章 算法在计算中的作用))
算法定义
输入输出
正确性
描述形式
典型问题
排序
最短路径
LCS
拓扑排序
凸包
DFT/FFT
数据结构
数组链表
散列表
树结构
高级结构
设计技术
分治
动态规划
贪心
摊还分析
多线程
难解问题
NP完全
近似算法
算法即技术
与硬件并列
性能决定五、重点与易错点
-
算法 vs 程序：算法是数学抽象，程序是实现；同一算法有多种程序实现。
-
不要混淆「候选解空间」与「解空间」：TSP 的解空间是 \(n!\) 条哈密尔顿回路，但候选解评估函数是路径总长度。
-
NP-complete 不是「不能解」，而是「没有已知的多项式算法」——常见误解是认为它们不可解。
-
数据结构选择是性能优化的第一步——不要写完算法再回头选数据结构。
-
分治 vs 动态规划：分治要求子问题独立；动态规划处理子问题重叠。
-
贪心不一定最优：活动选择问题贪心正确；0/1 背包问题贪心只给近似。
-
多线程算法的 speedup 受限于 span（阿姆达尔定律）：串行部分不能被并行化。
-
原书各章相互引用——遇到不清楚的概念时先看交叉引用章节，再回头精读。
-
第 1 章列举的所有问题（第 24 / 15 / 22 / 33 / 30 章）都会在后续章节详细解决——形成全书主轴。
-
「算法即技术」是第 1.2 节的核心论点：当性能成为瓶颈时，好的算法比硬件升级更经济。