第02章 入门 — 章节汇总

章节概览

第2章”入门”是《算法导论》正式进入算法设计与分析的第一章，由三节组成。2.1 插入排序以扑克牌整理为类比，完整展示了 INSERTION-SORT 伪代码，并通过循环不变式方法严格证明了算法正确性，同时系统阐述了全书使用的伪代码约定；2.2 算法分析引入 RAM 计算模型，以插入排序为例演示了逐行成本分析方法，推导出最好情况 $\Theta (n)$、最坏情况 $\Theta (n^2)$ 和平均情况 $\Theta (n^2)$ 的运行时间，并介绍了增长量级与 $\Theta$ 记号的非形式化定义；2.3 分治法系统介绍了分治算法设计范式，以归并排序为完整案例，展示了 MERGE 过程、递归关系式的建立与求解，以及递归树方法推导 $\Theta (n\lg n)$ 时间复杂度的全过程。全章建立了”算法设计—正确性证明—效率分析”三位一体的基本方法论，为后续深入学习奠定坚实基础。

---

2.1 插入排序 — 要点汇总

INSERTION-SORT 伪代码

• 核心思想：增量方法（incremental method），维护已排序子数组，每次将新元素插入正确位置
• 扑克牌类比：左手持已排序牌，右手逐一取牌插入正确位置
• 排序问题定义：输入 $n$ 个数的序列，输出满足非递减顺序的排列
• 关键字与卫星数据：被排序的数称为关键字（key），关联的其他数据称为卫星数据（satellite data），排序时记录随关键字一起移动

INSERTION-SORT(A, n)
1  for i = 2 to n
2      key = A[i]
3      // 将 A[i] 插入到已排序子数组 A[1 : i-1] 中
4      j = i - 1
5      while j > 0 and A[j] > key
6          A[j + 1] = A[j]
7          j = j - 1
8      A[j + 1] = key

循环不变式证明

循环不变式：在每次外层 for 循环迭代开始时，子数组 $A[1:i-1]$ 由原来在 $A[1:i-1]$ 中的元素组成，且已排好序。

性质	内容
初始化	$i=2$ 时，$A[1:1]$ 只含单个元素，天然有序
保持	循环体将 key 插入正确位置，$A[1:i]$ 变为有序，下次迭代 $i$ 递增后不变式成立
终止	$i=n+1$ 时，$A[1:n]$ 即整个数组已排序，算法正确

循环不变式与数学归纳法高度相似：初始化对应基础步，保持对应归纳步，终止利用终止条件得出最终结论。

伪代码约定

• 缩进表示块结构（无花括号）
• 循环计数器退出后保留值（for i = 2 to n 退出后 $i=n+1$）
• 1 起始下标（1-origin indexing），$A[i:j]$ 表示子数组
• 对象属性用点号访问（如 x.f），支持级联
• 标量按值传参，数组和对象传递指针
• and/or 为短路运算符
• NIL 表示空指针，error 表示立即终止

---

2.2 算法分析 — 要点汇总

RAM 模型

• 随机访问机（Random-Access Machine）：单处理器、串行执行
• 每条指令和数据访问均花费常数时间
• 数据类型：整数、浮点数、字符；布尔值用 0/非 0 表示
• 字长限制：整数通常为 $c\lg n$ 位
• 不包含内存层次结构（缓存、虚拟内存等）
• 灰色区域：指数运算 $2^n$ 一般不是常数时间操作

运行时间分析

• 输入规模：排序问题用元素数量 $n$；图问题用顶点数和边数
• 运行时间 $T(n)$：所有语句的”成本 $\times$ 次数”之和
• 以插入排序为例，设 $t_i$ 为 while 循环对每个 $i$ 的测试次数：

$T(n)=c_{1}n+c_2(n-1)+c_4(n-1)+c_5{\sum }_{i=2}^n{t}_i+c_6{\sum }_{i=2}^n(t_i-1)+c_7{\sum }_{i=2}^n(t_i-1)+c_8(n-1)$

最坏情况、最好情况与平均情况

情况	条件	$t_i$ 值	运行时间
最好情况	数组已排序	$t_i=1$	$T_{\text{best}}(n)=an+b=\Theta (n)$
最坏情况	数组逆序	$t_i=i$	$T_{\text{worst}}(n)=a{n}^2+bn+c=\Theta (n^2)$
平均情况	随机排列	$t_i\approx i/2$	$T_{\text{avg}}(n)=\Theta (n^2)$

通常关注最坏情况的三个原因：(1) 保证运行时间上界；(2) 最坏情况经常发生；(3) 平均情况通常与最坏情况同量级。

增长量级与 $\Theta$ 记号

• 增长量级：只保留最高阶项，忽略常数系数（如 $a{n}^2+bn+c\to n^2$）
• $\Theta$ 记号：$\Theta (n^2)$ 意味着”当 $n$ 较大时，大致正比于 $n^2$“（严格定义见第 3 章）
• 增长量级层次：$\Theta (1)<\Theta (\lg n)<\Theta (n)<\Theta (n\lg n)<\Theta (n^2)<\Theta (n^3)<\Theta (2^n)<\Theta (n!)$

---

2.3 分治法 — 要点汇总

分治法范式

分治法是一种递归式算法设计范式，每步执行三个操作：

步骤	英文	含义
分解	Divide	将问题划分为更小的子问题
解决	Conquer	递归求解子问题（规模足够小时直接求解 = 基准情况）
合并	Combine	将子问题的解合并为原问题的解

MERGE-SORT 与 MERGE 过程

• MERGE-SORT：计算中点 $q=\lfloor (p+r)/2\rfloor$，递归排序左右两半，调用 MERGE 合并
• 基准情况：$p\ge r$ 时（至多一个元素），直接返回
• MERGE：将两个有序子数组 $A[p..q]$ 和 $A[q+\mathrm{1..}r]$ 合并为有序的 $A[p..r]$，时间 $\Theta (n)$
• MERGE 使用临时数组 $L$ 和 $R$，通过三路 while 循环实现线性时间合并

递归关系式

归并排序的递归关系式：

$T(n)=2T(n/2)+\Theta (n)$

其中 $2T(n/2)$ 是递归求解两个规模为 $n/2$ 的子问题的代价，$\Theta (n)$ 是分解和合并的代价。

递归树方法

• 树的每一层代价均为 $c_{2}n$（节点数翻倍但每节点代价减半，恰好抵消）
• 总层数：$\lg n+1$
• 总代价：$c_{2}n\cdot \lg n+c_{1}n=\Theta (n\lg n)$
• 归并排序用 $\lg n$ 因子替换了插入排序的 $n$ 因子，对大规模输入优势显著

---

跨章关联

关联章节	关联内容	关联说明
第1章	插入排序与循环不变式的首次引入	第1章以插入排序为范例介绍算法概念，第2章深入展开其伪代码、正确性证明与复杂度分析
3.1 渐近记号	$\Theta$ 记号的严格定义	2.2 节非形式化引入 $\Theta$ 记号，第3章将给出 $O$、$\Omega$、$\Theta$ 的严格数学定义

---

笔记索引

节	笔记	核心主题
2.1	2.1 插入排序	INSERTION-SORT 伪代码、循环不变式、正确性证明、伪代码约定
2.2	2.2 算法分析	RAM 模型、最坏/最好/平均情况分析、增长量级、$\Theta$ 记号
2.3	2.3 分治法	分治范式、归并排序、MERGE 过程、递归关系式、递归树

第02章_入门