算法分析与设计第9讲 — 顺序算法分析的基本方法

北京大学屈婉玲教授《算法设计与分析》课程第9讲课程来源：田浩然上传的资料 / 0A002算法分析与设计关键词：算法分析、时间复杂度、空间复杂度、最优性、判定树、下界证明、搜索、排序、选择

一、算法分析的五大原则

1. 正确性

概念：给定有效输入后，算法经有限时间计算并产生正确答案。

两层证明：

方法的正确性 — 算法思路的正确性，证明相关引理、定理、公式
程序的正确性 — 证明指令序列确实做了所要求的工作

2. 工作量（时间复杂性）

计量标准：算法执行的基本运算次数（而非实际运行时间，与硬件无关）。

基本运算选择：

问题	基本运算
在表中查找 x	比较
实矩阵相乘	实数乘法
排序	比较
遍历二叉树	置指针

两种复杂性：

最坏情况 W(n) — 规模为 n 的输入中最大工作量
平均情况 A(n) — 各输入概率加权平均工作量

3. 占用空间（空间复杂性）

两类占用：

存储程序和输入数据的空间（通常 O(n)）
存储中间结果的额外空间（算法分析关注的重点）

原地工作算法：额外空间为常数 O(1)

4. 简单性

算法简单、程序结构简单
好处：易验证正确性、便于调试
简单 ≠ 高效，需在保证效率前提下追求简单

5. 最优性

含义：在求解某个问题的算法类中效率最高的算法。

两种最优性：

最坏情况下最优：没有其他算法在最坏情况下时间复杂度更低
平均情况下最优：没有其他算法在平均情况下时间复杂度更低

寻找最优算法的途径（上界 vs 下界逼近法）：

1. 设计算法 A，求 W(n)          → 给出上界
2. 寻找下界函数 F(n)            → 给出问题下界
3. 若 W(n) = F(n)，则 A 是最优的
4. 若 W(n) > F(n)，改进算法或提高下界
5. 重复直到二者相等

三种下界证明方法：

方法	核心思想	适用场景
判定树法	用二叉树建模算法，树深=最坏工作量，叶子数决定下界	搜索、排序等比较类问题
构造最坏输入法	构造特定输入使算法做最多非决定性操作	选择类问题
归约法	已知 Q 的下界，通过 Q≤P 证明 P 的下界	问题间复杂度关联

二、搜索有序表

顺序搜索

输入：有序数组 L[1..n]，待查找 x
输出：下标（找到）或 0（未找到）

1. j ← 1
2. while j ≤ n and L(j) ≠ x do j ← j+1
3. if j > n then j ← 0

复杂度：

最坏：W(n) = n
平均（等概率假设）：A(n) ≈ 3n/4

二分搜索

1. k ← 1; m ← n
2. while k ≤ m do
3.   j ← ⎣(k+m)/2⎦
4.   if x = L(j) then return j
5.   if x < L(j) then m ← j-1
6.   else k ← j+1
7. j ← 0

递推关系：W(n) = 1 + W(⎣n/2⎦), W(1) = 1

最坏复杂度：W(n) = ⎣log n⎦ + 1

平均复杂度（n = 2^k - 1）： A(n) ≈ ⎣log n⎦ + 1/2

搜索问题的下界 — 判定树模型

判定树定义：

每个内部节点标记为 L 的下标 i，表示 x 与 L(i) 比较
左儿子对应 x < L(i) 时下一步比较
右儿子对应 x > L(i) 时下一步比较
树深 = 最坏情况比较次数 - 1

关键引理：

二叉树第 t 层至多 2^t 个结点
深度为 d 的二叉树至多 2^(d+1) - 1 个结点
n 个结点的二叉树深度至少为 ⎣log n⎦

定理：任何搜索算法在最坏情况下至少要做 ⎣log n⎦ + 1 次比较。

→ 二分搜索在最坏情况下是最优的。

三、排序

三种主流排序算法对比

算法	最坏情况	平均情况	空间	特点
快速排序	O(n²)	O(n log n)	O(log n)	平均最快，最坏退化
归并排序	O(n log n)	O(n log n)	O(n)	稳定，需额外空间
堆排序	O(n log n)	O(n log n)	O(1)	原地，不稳定

堆排序详解

堆的定义：近似完全二叉树，每个结点元素 ≥ 儿子元素（大根堆）。

三大操作：

1. HEAPIFY(A, i) — 堆整理

将以 i 为根的子树调整为堆
时间：O(log n) 或 O(h)（h 为结点高度）
子堆大小至多为原堆的 2/3

2. BUILD-HEAP(A) — 建堆

for i ← ⎣n/2⎦ downto 1 do
    HEAPIFY(A, i)

定理：建堆时间为 O(n)（不是 O(n log n)）。

证明关键：高为 h 的结点数至多为 ⎡n / 2

3. HEAPSORT(A) — 堆排序

BUILD-HEAP(A)
for i ← n downto 2 do
    exchange A[1] ↔ A[i]
    heap-size ← heap-size - 1
    HEAPIFY(A, 1)

时间：O(n) + (n-1)·O(log n) = O(n log n)

排序问题的下界 — 判定树模型

排序判定树：每个内部节点是一次比较 (i, j)，每片叶子是一个排列。n 个元素有 n! 种排列，即 n! 片叶子。

引理：t 片树叶的 B-树深度至少为 ⎡log t⎤。

定理（最坏下界）：任何比较排序算法最坏情况下至少做 ⎡log n!⎤ 次比较，约为 n log n - 1.5n。

定理（平均下界）：等概率输入下，平均比较次数至少约为 n log n - 1.5n。

→ 堆排序和归并排序在阶上达到最优。

排序算法横向对比表

算法	最坏	平均	空间	最优性	稳定性
起泡排序	O(n²)	O(n²)	原地	否	稳定
快速排序	O(n²)	O(n log n)	O(log n)	平均最优	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	最优	稳定
堆排序	O(n log n)	O(n log n)	原地	最优	不稳定

四、选择问题

1. 选最大

算法：顺序扫描，打擂台
最坏：n - 1 次比较
下界：n - 1 次比较（一次比较最多淘汰一个数）
→ Findmax 是最优算法

2. 选最大和最小

朴素算法：分别找最大和最小 → 2n - 3 次比较

FindMaxMin 算法：成对比较优化

每对先互比（1次），大者与 max 比，小者与 min 比
每对 3 次比较，共 n/2 对 → 约 3n/2 次

最坏复杂度：⎡3n/2⎤ - 2 次比较

下界证明（状态构造法）：

数的四种状态：

N：未比较过
W：赢过（已知比某些数大）
L：输过（已知比某些数小）
WL：赢过且输过

每增加一个 W 或 L 提供 1 个信息单位，总共需要 2n-2 个信息单位。

比较前状态	比较后	增加信息单位
N, N	W, L	2
W, N	W, L	1
L, N	L, W	1
W, L	不变	0

→ 一次比较最多提供 2 个信息单位，至少有 ⎣n/2⎦ 次这样的比较 → 其余每次最多 1 个信息单位 → 总比较次数 ≥ ⎣n/2⎦ + (n-2) = ⎡3n/2⎤ - 2

→ FindMaxMin 是最优的

3. 选第二大

锦标赛方法：

用锦标赛法找最大（类似淘汰赛）
第二大一定是与 max 直接比较过的元素之一
从这些”输给 max 的选手”中再找最大

复杂度：n + ⎡log n⎤ - 2

下界证明（权值构造法）：

元素的权 w(x) = 以 x 为根的子树结点数
初始 w(x_i) = 1
每次胜者权 += 败者权
max 的权为 n，每次比较权最多翻倍
→ max 至少经过 ⎡log n⎤ 次比较
→ 第二大至少需要 ⎡log n⎤ - 1 次比较（从 max 的对手中选最大）

→ 锦标赛方法是找第二大的最优算法

4. 找中位数

Select 算法：O(n) 线性时间（最坏约 2.95n）

下界（定理）：任何比较找中位数的算法最坏情况下至少做 3n/2 - 3/2 次比较。

证明思路（决定性 vs 非决定性比较）：

决定性比较：建立了 x 与 median 的关系（x 已知大于或小于 median）
非决定性比较：x > median 且 y < median 时 x > y 的比较
必须做 n-1 次决定性比较
通过构造输入可使非决定性比较达到 (n-1)/2 次
总比较次数 ≥ (n-1) + (n-1)/2 = 3n/2 - 3/2

→ Select 算法在阶上达到最优

选择问题总结表

问题	算法	最坏情况	问题下界	最优性
找最大	Findmax	n - 1	n - 1	✅ 最优
找最大最小	FindMaxMin	⎡3n/2⎤ - 2	⎡3n/2⎤ - 2	✅ 最优
找第二大	锦标赛法	n + ⎡log n⎤ - 2	n + ⎡log n⎤ - 2	✅ 最优
找中位数	Select	O(n) ~ 2.95n	3n/2 - 3/2	✅ 阶最优
找第 k 小	Select	O(n)	n + min(k, n-k+1) - 2	✅ 阶最优

五、归约与问题复杂度

线性时间归约：若 Q 可在 O(n) 时间内转换成 P 的实例，则 P 至少和 Q 一样难（Q ≤_l P）。

经典归约示例：

Q（已知下界）	P（被证明下界）	归约方法
素数测试 Ω(W(n))	因式分解	用因子分解结果判定素性 → 因子分解至少和素数测试一样难
元素唯一性 Ω(n log n)	最邻近点对	将一维数值映射为 x 轴上的点，最短距离为 0 ↔ 不唯一 → 最邻近点对是 Ω(n log n)
元素唯一性 Ω(n log n)	最小生成树	n 个 x 轴点的 MST 最短边 = 0 ↔ 不唯一 → 最小生成树是 Ω(n log n)

六、本讲核心要点

算法分析五大维度：正确性、时间、空间、简单性、最优性
三种下界证明工具：判定树、构造最坏输入、归约
搜索最优：二分搜索最坏 ⎣log n⎦ + 1，达下界
排序最优：比较排序下界 ≈ n log n - 1.5n，归并排序/堆排序达阶最优
选择最优：最大(n-1)、最大最小(⎡3n/2⎤-2)、第二大(n+⎡log n⎤-2)均有精确最优算法；中位数线性时间阶最优
归约思想：通过已知问题的下界推导新问题的下界，是算法复杂度分析的核心技术之一

关联笔记：

原始文件：/田浩然上传的资料/0A002算法分析与设计/lecture9.pdf（395.85KB，70页，文字版PDF） 处理方式：pdftotext 全文提取，结构化梳理

知识库

探索

算法设计与分析第9讲 — 顺序算法分析的基本方法

算法分析与设计第9讲 — 顺序算法分析的基本方法

一、算法分析的五大原则

1. 正确性

2. 工作量（时间复杂性）

3. 占用空间（空间复杂性）

4. 简单性

5. 最优性

二、搜索有序表

顺序搜索

二分搜索

搜索问题的下界 — 判定树模型

三、排序

三种主流排序算法对比

堆排序详解

1. HEAPIFY(A, i) — 堆整理

2. BUILD-HEAP(A) — 建堆

3. HEAPSORT(A) — 堆排序

排序问题的下界 — 判定树模型

排序算法横向对比表

四、选择问题

1. 选最大

2. 选最大和最小

3. 选第二大

4. 找中位数

选择问题总结表

五、归约与问题复杂度

六、本讲核心要点

关系图谱

目录

反向链接

知识库

探索

算法设计与分析 第9讲 — 顺序算法分析的基本方法

算法分析与设计 第9讲 — 顺序算法分析的基本方法

一、算法分析的五大原则

1. 正确性

2. 工作量（时间复杂性）

3. 占用空间（空间复杂性）

4. 简单性

5. 最优性

二、搜索有序表

顺序搜索

二分搜索

搜索问题的下界 — 判定树模型

三、排序

三种主流排序算法对比

堆排序详解

1. HEAPIFY(A, i) — 堆整理

2. BUILD-HEAP(A) — 建堆

3. HEAPSORT(A) — 堆排序

排序问题的下界 — 判定树模型

排序算法横向对比表

四、选择问题

1. 选最大

2. 选最大和最小

3. 选第二大

4. 找中位数

选择问题总结表

五、归约与问题复杂度

六、本讲核心要点

关系图谱

目录

反向链接

算法设计与分析第9讲 — 顺序算法分析的基本方法

算法分析与设计第9讲 — 顺序算法分析的基本方法