第 2 章算法基础 (Getting Started)

核心结论

插入排序 (Insertion Sort)：以增量方式逐张将当前元素插入已排序子序列，最坏情况 \(\Theta(n^2)\)，最佳情况 \(\Theta(n)\)（已排序）。
循环不变量 (Loop Invariant)：证明算法正确性的核心方法——需验证 initialization / maintenance / termination 三个性质，类似数学归纳法。
RAM 计算模型：单处理器、随机访问、串行执行；每条指令常数时间；不模拟缓存与虚拟内存。本书绝大多数分析都在该模型下进行。
最坏情况与平均情况分析：最坏情况给出对所有输入的上界保证，是本书默认分析目标；平均情况往往与最坏同阶（如插入排序）。
增长量级 (Order of Growth)：忽略常数因子与低阶项，只看主项；插入排序 \(\Theta(n^2)\)，归并排序 \(\Theta(n \lg n)\)。
分治法与归并排序 (Divide-and-Conquer / Merge Sort)：把问题分解为更小子问题、递归求解、再合并；归并排序最坏情况 \(\Theta(n \lg n)\)，由递归式 \(T(n) = 2T(n/2) + \Theta(n)\) 刻画。
递归式 (Recurrence) 与递归树：递归式 + 递归树是分析分治算法运行时间的基本工具；本章用递归树直观地推出 \(T(n) = \Theta(n \lg n)\)。

本章主旨

本章用两个具体排序算法（插入排序、归并排序）展示算法设计与分析的全流程：伪代码约定 → 正确性证明（循环不变量）→ 运行时间分析（RAM 模型、最坏情况、增长量级）→ 设计与分析更高性能的分治算法 → 用递归树理解分治算法的复杂度。第 3 章将给出 Θ 记号的精确定义；第 4 章给出递归式的系统解法（主定理）。

一、核心概念

本章围绕 6 个核心概念展开：先通过插入排序引入伪代码与循环不变量，再用 RAM 模型与增长量级建立分析框架，最后以分治法和归并排序引出递归式与递归树。

概念	定义 + 重要性	实现提示
插入排序 (Insertion Sort)	增量算法：每步把一张牌插入手中已排序的正确位置；最坏 \(\Theta(n^2)\)，最佳 \(\Theta(n)\)。	§2.1；原地排序 (in-place)；伪代码 INSERTION-SORT（8 行）。
循环不变量 (Loop Invariant)	在每次循环迭代开始时成立的命题；正确性证明需验证三条性质：初始化、保持、终止。	§2.1；类比数学归纳法（base case = initialization；inductive step = maintenance）。
RAM 模型与运行时间	单处理器顺序执行的计算模型；每行伪代码常数时间；运行时间 = 各语句执行次数 × 成本的累加。	§2.2；最佳 / 最坏 / 平均情况分别对应输入的特定条件或分布假设。
增长量级 (Order of Growth) / Θ 记号	忽略常数因子与低阶项后，函数的主要增长趋势；用来横向比较算法效率。	§2.2；插入排序 \(\Theta(n^2)\) vs 归并排序 \(\Theta(n \lg n)\)。
分治法 (Divide-and-Conquer)	把问题分解为独立子问题，递归求解后合并；三步：Divide / Conquer / Combine。	§2.3.1；归并排序是教科书例子，第 4 章给出系统分析。
递归式与递归树 (Recurrence / Recursion Tree)	递归式用 \(T(n)\) 在小子问题上的值刻画 \(T(n)\)；递归树把递归式展开为树状图，逐层求和得到增长量级。	§2.3.2；归并排序：\(T(n) = 2T(n/2) + \Theta(n)\) → \(\Theta(n \lg n)\)。

概念

定义 + 重要性

实现提示

插入排序 (Insertion Sort)

增量算法：每步把一张牌插入手中已排序的正确位置；最坏 \(\Theta(n^2)\)，最佳 \(\Theta(n)\)。

§2.1；原地排序 (in-place)；伪代码 INSERTION-SORT（8 行）。

循环不变量 (Loop Invariant)

在每次循环迭代开始时成立的命题；正确性证明需验证三条性质：初始化、保持、终止。

§2.1；类比数学归纳法（base case = initialization；inductive step = maintenance）。

RAM 模型与运行时间

单处理器顺序执行的计算模型；每行伪代码常数时间；运行时间 = 各语句执行次数 × 成本的累加。

§2.2；最佳 / 最坏 / 平均情况分别对应输入的特定条件或分布假设。

增长量级 (Order of Growth) / Θ 记号

忽略常数因子与低阶项后，函数的主要增长趋势；用来横向比较算法效率。

§2.2；插入排序 \(\Theta(n^2)\) vs 归并排序 \(\Theta(n \lg n)\)。

分治法 (Divide-and-Conquer)

把问题分解为独立子问题，递归求解后合并；三步：Divide / Conquer / Combine。

§2.3.1；归并排序是教科书例子，第 4 章给出系统分析。

递归式与递归树 (Recurrence / Recursion Tree)

递归式用 \(T(n)\) 在小子问题上的值刻画 \(T(n)\)；递归树把递归式展开为树状图，逐层求和得到增长量级。

§2.3.2；归并排序：\(T(n) = 2T(n/2) + \Theta(n)\) → \(\Theta(n \lg n)\)。

二、详细笔记

2.1 插入排序 (Insertion Sort)

What：增量式排序——维护一个已排序的左侧子数组 \(A[1{:}j-1\)]，把元素 \(A[j\)] 插入其中的正确位置。

Why：插入排序是第一个具体算法实例，体现「算法 → 伪代码 → 正确性 → 复杂度」的完整链路；同时它是「最佳情况 vs 最坏情况」差异的经典例子。

How：

伪代码（INSERTION-SORT, §2.1）：

\[\begin{array}{rl} 1 & \textbf{for } j = 2 \textbf{ to } A.\text{length} \\ 2 & \quad key = A[j] \\ 3 & \quad \text{// Insert } A[j] \text{ into the sorted sequence } A[1{:}j-1] \\ 4 & \quad i = j - 1 \\ 5 & \quad \textbf{while } i > 0 \textbf{ and } A[i] > key \\ 6 & \quad \quad A[i+1] = A[i] \\ 7 & \quad \quad i = i - 1 \\ 8 & \quad A[i+1] = key \end{array}\]

循环不变量（§2.1）：在 for 循环每次迭代开始时，子数组 \(A[1{:}j-1\)] 由原数组 \(A[1{:}j-1\)] 的元素组成，但已按序排列。

When：小数据量、几乎有序、在线输入（流式插入）；当比较操作代价远小于移动操作时表现尤佳。

Example：插入排序对 \(\langle 5, 2, 4, 6, 1, 3 \rangle\) 的逐步执行见图 2.2 — 每次插入产生一个更长的已排序前缀。

2.2 循环不变量与正确性证明

What：循环不变量是「在循环每次迭代开始时成立的命题」，用来证明带循环的算法的正确性。

Why：直接跟踪所有可能的输入路径困难；循环不变量把整个运行过程压缩为「在某个点上恒成立」的命题——只需验证三件事即可证明整个算法正确。

How：三条性质

初始化 (Initialization)：循环第一次迭代开始时，不变量为真。
保持 (Maintenance)：若迭代开始时不变量为真，则下一次迭代开始前仍为真。
终止 (Termination)：循环终止时，不变量 + 终止条件 → 有用性质（通常即算法正确性）。

类似数学归纳法：base case = initialization；inductive step = maintenance。区别在于归纳步只需执行有限次，到 termination 即停。

When：任何带 for / while 循环的算法都可用循环不变量证明正确性——插入排序（第 2 章）、归并排序的 MERGE 子程序（第 2 章）、堆操作（第 6 章）、快速排序的 PARTITION（第 7 章）都遵循此模式。

Example：插入排序的不变量（§2.1）：

初始化：\(j = 2\)，子数组 \(A[1{:}1\)] = 原数组的 \(A[1\)]，单元素天然有序 → 真。
保持：内层 while 把 \(A[j\)] 插入 \(A[1{:}j-1\)] 的正确位置 → 迭代后 \(A[1{:}j\)] 已排好序。
终止：\(j = n+1\)，不变量给出 \(A[1{:}n\)] 已排好序 → 整个数组有序。

2.3 RAM 模型与算法分析

What：RAM (Random-Access Machine) 模型是本书采用的计算模型——单处理器顺序执行，指令包括算术、数据移动、控制；每条指令常数时间。

Why：分析算法需要明确的「机器」概念；RAM 模型简单、抽象、与现实计算机一致；让运行时间成为输入大小的函数，可以脱离具体硬件比较算法。

How：运行时间定义（§2.2）：

输入规模 (Input Size)：排序用元素数 \(n\)；整数乘法用位数；图用顶点数 + 边数。
运行时间 (Running Time)：算法执行的「基本操作」或「步骤」数；本书假设每行伪代码一次执行占常数时间 \(c_i\)。
总运行时间：\(T(n) = \sum_i c_i \cdot (\text{执行次数})\)。

When：分析所有算法时默认使用 RAM 模型；少数情况下（如外部存储算法、并行算法）需要更精细的模型，但不在本章范围。

Example：插入排序的最坏情况分析（§2.2）：设 \(t_j\) = while 循环在第 \(j\) 次外层迭代中的执行次数。最坏情况（逆序）下 \(t_j = j\)，得到：

\[T(n) = \left(\tfrac{c_5}{2} + \tfrac{c_6}{2} + \tfrac{c_7}{2}\right) n^2 + (c_1 + c_2 + c_4 + \tfrac{c_5}{2} - \tfrac{c_6}{2} - \tfrac{c_7}{2} + c_8) n - (c_2 + c_4 + c_5 + c_8)\]

因此 \(T(n) = an^2 + bn + c\)，即 \(\Theta(n^2)\)；最佳情况（已排序）下 \(t_j = 1\)，得 \(T(n) = an + b\) = \(\Theta(n)\)。

2.4 最佳、最坏与平均情况分析

What：对同一规模的输入，不同实例可能产生不同运行时间；通常用最坏情况（worst case）、最佳情况（best case）、平均情况（average case）刻画。

Why：最坏情况给出对所有输入的上界保证——「无论怎样输入，运行时间都不会超过这个值」；平均情况刻画「典型」输入下的行为，但需要明确输入分布假设。

How：三种情况的选取（§2.2）：

最坏情况：所有规模为 \(n\) 的输入中运行时间的最大值；本章及全书的默认目标。
最佳情况：所有规模为 \(n\) 的输入中运行时间的最小值；通常给出平凡下界。
平均情况：在某个输入分布下（如「所有输入等概率」）运行时间的期望；需要概率工具（第 5 章深入讨论）。

理由：

最坏情况给出上界——无需猜测。
最坏情况常出现（数据库查找未命中）。
平均情况常与最坏同阶（如插入排序）。

When：

选最坏情况分析时：当需要性能保证、或者平均分布不明确时。
选平均情况分析时：输入分布已知且算法对分布敏感（如随机化算法的期望运行时间）。
选最佳情况分析时：通常只用于证伪下界（证明算法不是某个增长量级）。

Example：插入排序（§2.2）

最佳：\(\Theta(n)\)，输入已排序。
最坏：\(\Theta(n^2)\)，输入逆序。
平均：\(\Theta(n^2)\)，约一半元素需要移动，每轮 while 平均迭代 \(j/2\) 次。

线性搜索（练习 2.1-3）：

最佳：\(\Theta(1)\)，目标元素恰在首位。
最坏：\(\Theta(n)\)，目标不在或位于末位。
平均：\(\Theta(n)\)，目标等概率出现在任意位置。

2.5 增长量级 (Order of Growth) 与 Θ 记号

What：增长量级只关注主项、忽略常数因子与低阶项；用 Θ 记号 \(\Theta(g(n))\) 表示「与 \(g(n)\) 同阶」的所有函数的集合。

Why：对于大输入，常数因子与低阶项相对主项不重要；增长量级让算法比较变得简单（\(\Theta(n \lg n)\) vs \(\Theta(n^2)\)）。本章给出 Θ 的非形式化用法，第 3 章给出精确定义。

How：化简步骤

把 \(T(n)\) 写成多项式：\(T(n) = a n^2 + bn + c\)。
只保留最高阶项：\(\sim an^2\)。
去掉常数：\(\Theta(n^2)\)。

When：比较两个算法的「渐近效率」时；预测大输入下的行为；选择合适算法时（插入 vs 归并）。

Example：多项式 \(\tfrac{n^3}{1000} - 100 n^2 - 100 n + 3\) 的增长量级是 \(\Theta(n^3)\)（练习 2.2-1）。

2.6 分治法 (Divide-and-Conquer) 与归并排序

What：分治法把问题分解为更小子问题（与原问题同型但更小），递归求解，再合并。三步：

Divide：把问题分解为若干子问题。
Conquer：递归求解子问题；若子问题足够小则直接求解。
Combine：把子问题的解合并为原问题的解。

归并排序 (Merge Sort) 是教科书例子（§2.3.1）：

Divide：把 \(n\) 元序列分为两个 \(n/2\) 元子序列。
Conquer：递归排序两个子序列。
Combine：MERGE 子程序把两个已排序子序列合并为一个。

Why：分治是本书后续算法的基础设计范式（最大子数组、Strassen 矩阵乘、FFT 等）；相比增量法（插入排序）通常能得到更好的渐近复杂度。

How：MERGE 子程序伪代码（§2.3.1）：

\[\begin{array}{rl} 1 & n_1 = q - p + 1 \\ 2 & n_2 = r - q \\ 3 & \text{let } L[1{:}n_1+1] \text{ and } R[1{:}n_2+1] \text{ be new arrays} \\ 4 & \text{for } i = 1 \text{ to } n_1: L[i] = A[p+i-1] \\ 5 & \text{for } j = 1 \text{ to } n_2: R[j] = A[q+j] \\ 6 & L[n_1+1] = R[n_2+1] = \infty \quad \text{(哨兵)} \\ 7 & i = j = 1 \\ 8 & \text{for } k = p \text{ to } r \\ 9 & \quad \textbf{if } L[i] \leq R[j]: A[k] = L[i++], \textbf{else}: A[k] = R[j++] \end{array}\]

哨兵 (sentinel) 是放置在每个子数组末尾的特殊值（通常 \(\infty\)），消除每次比较「是否还有元素」的边界检查。MERGE 运行时间为 \(\Theta(n)\)，其中 \(n = r - p + 1\)。

MERGE-SORT 顶层（§2.3.1）：

\[\begin{array}{rl} 1 & \textbf{if } p < r \\ 2 & \quad q = \lfloor (p+r)/2 \rfloor \\ 3 & \quad \text{MERGE-SORT}(A, p, q) \\ 4 & \quad \text{MERGE-SORT}(A, q+1, r) \\ 5 & \quad \text{MERGE}(A, p, q, r) \end{array}\]

When：分治法适用条件——子问题独立（无重叠）+ 合并代价可控。当子问题有重叠时，应用动态规划（第 15 章）而非分治。

Example：归并排序对 \(\langle 5, 2, 4, 7, 1, 3, 2, 6 \rangle\) 的执行见图 2.4 — 自底向上把相邻有序段两两合并，最后一次合并产生整个有序序列。

2.7 递归式与递归树 (Recurrence / Recursion Tree)

What：递归式是「函数用其在更小输入上的值刻画自己」的方程或不等式。递归树把递归式展开为树形结构，每层表示同一深度的所有子问题的总代价。

Why：递归式自然刻画分治算法的运行时间；递归树提供直观解法——逐层求和。本章先看递归树；第 4 章给出三种系统方法（代入法、递归树法、主定理）。

How：分治算法运行时间的通用递归式（§2.3.2）：

\[T(n) = \begin{cases} \Theta(1) & \text{if } n \leq c \\ aT(n/b) + D(n) + C(n) & \text{otherwise} \end{cases}\]

其中：

\(a\) = 子问题数；
\(1/b\) = 子问题相对原问题的规模比例；
\(D(n)\) = divide 步骤代价；
\(C(n)\) = combine 步骤代价。

归并排序的具体递归式（式 2.1）：

\[T(n) = \begin{cases} \Theta(1) & \text{if } n = 1 \\ 2T(n/2) + \Theta(n) & \text{if } n > 1 \end{cases}\]

递归树法（§2.3.2，图 2.5）：

树根 = \(cn\)（顶层代价）。
每个内部节点 = 子问题的 combine 代价；左右子树 = 子问题的递归开销。
叶子层 = \(n\) 个基础情形节点，每个 \(c\)。
树高度 = \(\lg n + 1\)（当 \(n\) 是 2 的幂时）。
每层总代价 = \(cn\)（因为 \(2^i \cdot c(n/2^i) = cn\)）。
总代价 = \(cn \cdot (\lg n + 1) = cn \lg n + cn = \Theta(n \lg n)\)。

When：

递归式 — 任何递归算法的运行时间描述。
递归树 — 当主定理（§4.5）不适用、或需要直观理解时的工具；也是主定理证明的核心。

Example：归并排序递归树（图 2.5）— \(n\) 层 × 每层 \(cn\) = \(\Theta(n \lg n)\)。

三、关键图表

本章无独立编号图表

本章的核心算法（插入排序、归并排序、MERGE）和递归树都依赖原书图 2.1–2.5 的图形说明，本笔记以伪代码 + 公式 + 文字描述形式呈现；原书图示可参见 CLRS 第 4 版第 17–37 页。

核心公式对照表

式编号

内容

式 2.1

归并排序最坏运行时间递归式：\(T(n) = 2T(n/2) + \Theta(n)\), \(T(1) = \Theta(1)\)

式 2.2

简化版：\(T(n) = 2T(n/2) + cn\), \(T(1) = c\)

§2.2 插入排序最佳

\(T(n) = an + b = \Theta(n)\)（已排序）

§2.2 插入排序最坏

\(T(n) = an^2 + bn + c = \Theta(n^2)\)（逆序）

§2.2 求和公式

\(\sum_{j=2}^n j = \frac{n(n+1)}{2} - 1\)，\(\sum_{j=2}^n (j-1) = \frac{n(n-1)}{2}\)

四、思维导图

mindmap
  root((第 2 章 算法基础))
    插入排序
      增量插入
      伪代码8行
      原地排序
    循环不变量
      初始化
      保持
      终止
      类比归纳法
    RAM模型
      单处理器
      常数指令
      步骤计数
    情况分析
      最坏
      平均
      最佳
    增长量级
      主项
      忽略常数
      Θ记号
    分治法
      Divide
      Conquer
      Combine
    归并排序
      MERGE
      哨兵技巧
      Θ(n lg n)
    递归式
      树状展开
      逐层求和

五、重点与易错点

伪代码不是程序：忽略软件工程细节（模块化、错误处理、数据抽象）；伪代码的目标是「清晰传达算法本质」。
循环不变量的三条性质缺一不可：termination 不是数学归纳法的无限归纳步，而是「有限次归纳后给出一个有用的性质」。
插入排序的最佳 vs 最坏：已排序 = \(\Theta(n)\)；逆序 = \(\Theta(n^2)\)。许多初学者误以为是「永远 \(\Theta(n^2)\)」。
RAM 模型是抽象：不模拟缓存、虚拟内存、并行；第 27 章的多线程算法模型扩展了 RAM。
增长率 vs 常数因子：对大输入，增长率决定一切；对小输入，常数因子可能让 \(\Theta(n^2)\) 算法跑得比 \(\Theta(n \lg n)\) 还快（练习 2-1：归并排序里对小段改用插入排序）。
分治 vs 增量：插入排序是增量（每次处理 1 个新元素）；归并排序是分治（每次分两半再合并）。
MERGE 的哨兵：哨兵消除「数组是否已读完」的边界检查，让主循环更简洁；复杂度仍是 \(\Theta(n)\)（额外常数倍）。
分治三步的代价：Divide 通常 \(\Theta(1)\)；Conquer 是递归本身（捕获在 \(T(n/b)\) 项）；Combine 是 MERGE 等子程序的代价（\(\Theta(n)\)）。
递归树的层数：当 \(n\) 是 2 的幂时为 \(\lg n + 1\)；一般情况 \(\lfloor \lg n \rfloor + 1\)，同阶。
归并排序的最坏/最佳/平均都是 \(\Theta(n \lg n)\)：这是它相对插入排序的核心优势——「稳定的最坏情况性能」。
「分析」不是「实现」：本章的「步骤」是抽象的操作计数；实际运行还受缓存、流水线、编译器等影响，但渐近分析是可靠的预测。
排序问题的形式化（再次出现）：输入 \(\langle a_1, \ldots, a_n \rangle\)，输出重排使得 \(a'_1 \leq a'_2 \leq \cdots \leq a'_n\)——第 1 章已给出，本章两个算法都解决这个问题但效率差 \(\Theta(\lg n)\) 倍。

第 2 章 算法基础 (Getting Started)