第01章 算法在计算中的角色 - 章节汇总

章节概览

第1章是《算法导论》的开篇导论，由两节组成。1.1 算法给出了算法的形式化定义，以插入排序为范例演示了伪代码描述与循环不变式正确性证明；1.2 算法作为一种技术论证了算法效率可以压倒硬件优势的核心观点。全章旨在建立”算法是解决问题的精确工具”与”算法本身就是一种核心技术”两个基本认知，为后续深入学习算法设计与分析奠定观念基础。

---

1.1 算法 - 要点汇总

算法的定义

• 非形式化定义：算法是一个良定义的计算过程，接受输入（input）并产生输出（output），是解决特定计算问题的工具
• 形式化定义：算法将输入映射为输出，排序问题的输入为 $⟨a_1,a_2,\dots ,a_n⟩$，输出为满足 $a_1^{\prime }\le a_2^{\prime }\le \cdots \le a_n^{\prime }$ 的排列
• 正确性要求：算法必须对所有合法输入实例都能在有限时间内终止并给出正确答案

INSERTION-SORT 示例

• 插入排序的工作原理：从第二个元素开始，将每个元素插入到已排序子序列的正确位置
• 伪代码描述：外层循环遍历 $j=2$ 到 $n$，内层 while 循环将 $A[j]$ 向左移动到正确位置
• 时间复杂度：最好情况 $O(n)$（已排序），最坏/平均情况 $O(n^2)$

循环不变式（Loop Invariant）

循环不变式是证明循环型算法正确性的核心方法，需满足三个性质：

性质	含义	对应时机
初始化（Initialization）	循环第一次迭代前，不变式为真	循环开始前
保持（Maintenance）	若某次迭代前不变式为真，则下次迭代前仍为真	每次迭代中
终止（Termination）	循环终止时，不变式提供有用性质证明算法正确性	循环结束后

对于插入排序，循环不变式为：在每次外层循环迭代开始时，子数组 $A[\mathrm{1..}j-1]$ 由原来在 $A[\mathrm{1..}j-1]$ 中的元素组成，且已排好序。

其他要点

• 算法广泛应用于基因组计划、互联网路由、电子商务、资源分配等领域
• NP完全问题是尚未找到多项式时间算法的困难问题集合
• 数据结构是存储和组织数据的方式，与算法共同构成程序设计的两大支柱

---

1.2 算法作为一种技术 - 要点汇总

核心论点：算法效率压倒硬件优势

• 计算时间是有界资源，时间比金钱更宝贵
• 插入排序 $O(n^2)$ vs 归并排序 $O(n\lg n)$：增长量级的差异随 $n$ 增大而急剧放大

经典对比实验

场景	计算机 A（快）	计算机 B（慢）
硬件速度	基准速度	慢 1000 倍
排序算法	插入排序 $c_1{n}^2$	归并排序 $c_{2}n\lg n$
排序 1000 万个数	基准时间	比 A 快 17 倍以上
排序 1 亿个数	超过 23 天	不到 4 小时

关键结论

一台慢 1000 倍的计算机，仅因为使用了更优的算法（归并排序 vs 插入排序），就能在处理大规模数据时取得压倒性优势。算法效率的差异可以轻易超过硬件性能的差异。

算法与其他技术的关系

• 硬件设计、GUI、网络路由、编译器等大多数计算机技术都以算法为核心基础
• 机器学习本身就是一组算法；对于人类理解透彻的问题，精心设计的算法通常优于机器学习方法
• 算法知识是优秀程序员的核心标志

---

跨章关联

关联章节	关联内容	关联说明
第2章 入门	归并排序的分治实现、递归分析	1.1 提到分治法与归并排序，第2章将完整展开
第3章 运行时间刻画	渐近记号（$O$、$\Omega$、$\Theta$）	1.2 使用 $O(n^2)$、$O(n\lg n)$ 等记号，第3章将严格定义

---

笔记索引

节	笔记	核心主题
1.1	1.1 算法	算法定义、插入排序、循环不变式、正确性证明
1.2	1.2 算法作为一种技术	算法效率、硬件 vs 算法加速、排序对比实验

第01章_算法在计算中的角色