COMP2013 数据结构与算法教程：从复杂度分析、排序、堆、哈希、搜索树到 DP、贪心与图

这篇文章根据 COMP2013 Data Structures and Algorithms 的课程资料整理。它不是单纯把 lecture 列出来，而是试图回答一个更重要的问题：

当我们说“学数据结构与算法”时，到底是在训练什么能力？

我的理解是三件事。第一，能判断一个程序会不会随着输入规模变大而崩掉，也就是复杂度分析。第二，能选择合适的数据组织方式，让查询、插入、删除、排序这些操作不至于低效。第三，能把一个问题拆成可以证明正确的算法框架，比如分治、动态规划、贪心和图搜索。

原始资料下载

• COMP2013 全部资料压缩包
• Lecture 1: Introduction
• Lecture 2: Analysis of Algorithms and Merge Sort
• Lecture 3: Divide and Conquer
• Lecture 4: Sorting Algorithms
• Lecture 5: Binary Heap
• Lecture 6: Elementary Data Structures
• Lecture 7: Hashing and BST I
• Lecture 8: BST II
• Lecture 9: Balanced BST
• Lecture 10: Dynamic Programming
• Lecture 11: Greedy Algorithms
• Lecture 12: Graphs
• Assignment 1: Recurrence Analysis
• Assignment 2 Code: Minimum Difference by Merge Sort
• Assignment 3: Trees and Hashing

1. 数据结构与算法的主线

一个算法问题通常可以写成：

input -> data representation -> operations -> output

比如“给定一组整数，找出排序后相邻元素的最小差值”。输入是一个整数数组，数据表示可以是普通数组，核心操作是排序和扫描，输出是一个最小差值。这个问题看起来简单，但它已经包含算法课最重要的两层思维：

1. 如果暴力枚举任意两个数的差值，需要比较大约 (n(n-1)/2) 对，复杂度是 (O(n^2))。
2. 如果先排序，只需要比较相邻元素，排序 (O(n\log n))，扫描 (O(n))，总复杂度是 (O(n\log n))。

为什么排序后只需要看相邻元素？因为在有序序列中，如果 (a_i \le a_j \le a_k)，那么 (a_k-a_i) 一定不会小于中间的相邻差值。最小差值一定被某一对相邻元素捕获。这就是算法里很常见的思路：先改变数据的结构，再让问题变简单。

2. 复杂度：算法为什么要关心增长率

算法分析关心的不是程序在某台电脑上跑了几秒，而是输入规模 (n) 增大时，运行时间如何增长。

常见复杂度可以按增长速度理解：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

这几个级别的差异非常大。假设 (n=1,000,000)：

• (O(1))：常数次操作。
• (O(\log n))：大约二十次左右，二分搜索就是典型例子。
• (O(n))：一百万次，线性扫描。
• (O(n\log n))：两千万级别，归并排序、堆排序常见。
• (O(n^2))：一万亿级别，很多双重循环会到这里。

算法课里的第一个转变，是不要只问“这段代码对不对”，还要问：

这段代码在输入变大后还能不能活？

3. 递推式：递归算法的复杂度怎么推

分治算法经常产生递推式。比如归并排序：

$$T(n)=2T(n/2)+O(n)$$

意思是：把数组分成两半，各自排序，然后用线性时间合并。递归树可以这样理解：

• 第 0 层：一个规模 (n) 的问题，合并代价 (n)。
• 第 1 层：两个规模 (n/2) 的问题，总合并代价 (2 \cdot n/2=n)。
• 第 2 层：四个规模 (n/4) 的问题，总合并代价 (4 \cdot n/4=n)。
• 一直到问题规模变成 1，层数是 (\log_2 n)。

每一层代价都是 (n)，共有 (\log n) 层，所以：

$$T(n)=O(n\log n)$$

作业里也有类似递推：

$$T(n)=5T(n/3)+2n$$

递归树第 (i) 层有 (5^i) 个子问题，每个子问题规模是 (n/3^i)，每个子问题的非递归代价与规模成正比，所以第 (i) 层总代价是：

$$5^i \cdot 2(n/3^i)=2n(5/3)^i$$

递归深度由 (n/3^k=1) 得到：

$$k=\log_3 n$$

总成本是一个等比级数：

$$\sum_{i=0}^{\log_3 n}2n(5/3)^i$$

最后一层占主导，因此：

$$T(n)=O(n^{\log_3 5})$$

这个例子很重要，因为它说明递归不一定都是 (n\log n)。分裂数量、子问题规模和合并代价共同决定结果。

4. 分治：把大问题拆成同类小问题

分治算法有三个步骤：

Divide -> Conquer -> Combine

典型例子有：

• Binary Search：每次丢掉一半搜索空间。
• Merge Sort：把数组分成两半，分别排序后合并。
• Maximum Subarray：最大子数组要么在左边，要么在右边，要么跨过中点。

二分搜索的复杂度是 (O(\log n))。如果一个有序数组长度为 (n)，每次搜索范围减半，经过 (k) 次后剩下 (n/2^k) 个元素。当只剩一个元素时：

$$n/2^k=1$$

所以：

$$k=\log_2 n$$

二分搜索的本质不是“取中点”，而是利用有序性排除大量不可能的答案。没有有序性，二分就没有基础。

5. 排序：为什么排序是算法课的核心

排序不只是为了把数字排好看。排序经常是很多问题的前置结构化步骤。

常见排序可以这样比较：

算法	思想	平均复杂度	最坏复杂度	稳定性
Insertion Sort	维护已排序前缀	(O(n^2))	(O(n^2))	稳定
Merge Sort	分治合并	(O(n\log n))	(O(n\log n))	稳定
Quick Sort	选 pivot 分区	(O(n\log n))	(O(n^2))	通常不稳定
Heap Sort	用堆反复取最大值	(O(n\log n))	(O(n\log n))	不稳定

比较排序有一个重要下界：

$$\Omega(n\log n)$$

直观理解是：如果只通过比较判断元素顺序，那么所有可能排列有 (n!) 种。每次比较最多把可能性分成两部分，一棵比较决策树至少要有 (n!) 个叶子，所以高度至少是：

$$\log_2(n!)=\Omega(n\log n)$$

这说明 Merge Sort 和 Heap Sort 在比较排序模型里已经达到渐进最优。除非利用额外信息，比如整数范围很小，才可能用 Counting Sort 这类非比较排序做到线性时间。

6. 作业例子：用 Merge Sort 做最小相邻差值

资料里有一份 C++ 作业代码，目标是从文件读入数字，排序后找最小相邻差值。核心思路可以整理成更干净的版本：

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDifference(const string& filename) {
    ifstream file(filename);
    int n;
    file >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        file >> a[i];
    }

    sort(a.begin(), a.end());

    int ans = a[1] - a[0];
    for (int i = 1; i + 1 < n; ++i) {
        ans = min(ans, a[i + 1] - a[i]);
    }
    return ans;
}

int main() {
    string filename;
    cin >> filename;
    cout << minDifference(filename);
    return 0;
}

如果课程要求手写 Merge Sort，也可以不用 std::sort，但工程上优先使用标准库。这里真正要学的是：

1. 先排序，把“任意两数比较”变成“只比较相邻数”。
2. 排序是主成本，复杂度 (O(n\log n))。
3. 扫描只需要 (O(n))。
4. 文件输入要处理好数组大小和边界情况，例如 (n<2) 时没有差值可算。

这个例子也提醒一点：算法作业里经常会先训练“自己实现”，但真实项目里要知道什么时候用标准库。能手写是理解，能用库是工程能力。

7. 堆：优先级队列背后的数据结构

Binary Heap 可以理解成存在数组里的完全二叉树。对于下标从 1 开始的堆：

parent(i) = floor(i / 2)
left(i)   = 2i
right(i)  = 2i + 1

Max-Heap 满足：

每个节点的 key >= 它的子节点 key

所以根节点永远是最大值。堆支持几个关键操作：

• Max：取最大值，(O(1))。
• Extract-Max：删除最大值并恢复堆，(O(\log n))。
• Insert：插入新元素并向上调整，(O(\log n))。
• Build-Heap：从数组建堆，(O(n))。

为什么 Build-Heap 是 (O(n))，不是 (O(n\log n))？因为并不是每个节点都要下沉 (\log n) 层。底层节点很多，但下沉距离很短；顶层节点很少，虽然可能下沉很远。把所有节点的下沉成本加起来是线性的。

堆最常见的应用是 Priority Queue，比如任务调度、Dijkstra 最短路、Top-K 问题。面试里如果看到“不断取当前最大/最小”，第一反应就应该想到堆。

8. 基础数据结构：数组、链表、栈、队列

Lecture 6 进入基础数据结构。它们看起来朴素，但几乎是所有复杂结构的零件。

数组的特点：

• 支持随机访问，a[i] 是 (O(1))。
• 插入和删除中间元素通常是 (O(n))，因为要移动元素。
• 适合连续存储、频繁按下标访问的场景。

链表的特点：

• 插入和删除已知节点可以是 (O(1))。
• 访问第 (i) 个元素是 (O(n))，因为要从头走。
• 适合频繁插入删除、但不需要随机访问的场景。

栈是后进先出：

push -> push -> pop

常见应用包括函数调用栈、括号匹配、DFS、表达式求值。

队列是先进先出：

enqueue -> enqueue -> dequeue

常见应用包括 BFS、任务队列、缓冲区。

学这些结构时，不要只背接口，要问两个问题：

1. 它把什么操作变快了？
2. 它牺牲了什么操作？

数据结构没有绝对好坏，只有是否适合当前操作模式。

9. 哈希表：用空间换平均常数时间

哈希表的目标是让搜索、插入、删除在平均情况下接近 (O(1))。核心是哈希函数：

$$h(k)=k \bmod m$$

它把 key 映射到长度为 (m) 的表中。但不同 key 可能映射到同一位置，这叫 collision。

解决冲突常见方法：

• Chaining：每个桶挂一个链表。
• Open Addressing：如果位置被占，就按探测序列找下一个位置。
• Linear Probing：线性探测。
• Quadratic Probing：平方探测。
• Double Hashing：用第二个哈希函数决定步长。

哈希表的关键指标是 load factor：

$$\alpha = n/m$$

其中 (n) 是元素数量，(m) 是表大小。负载因子太高，冲突会变多，哈希表会退化。工程里的 unordered_map、Python 的 dict 都会在必要时扩容，背后就是为了控制负载因子。

哈希表适合回答“某个 key 是否存在”“某个 key 对应什么值”。但它不维护顺序。如果你需要 predecessor、successor、范围查询，搜索树通常更合适。

10. 二叉搜索树：用顺序结构支持动态查询

Binary Search Tree 满足：

左子树 key <= 当前节点 key <= 右子树 key

它支持：

• Search
• Minimum / Maximum
• Predecessor / Successor
• Insert
• Delete

这些操作的复杂度都是：

$$O(h)$$

其中 (h) 是树高。如果树平衡，(h=O(\log n))；如果不断插入递增序列，树会退化成链表，(h=O(n))。

这就是为什么 Lecture 9 要讲 Balanced Binary Search Tree。平衡树的目标不是改变 BST 的有序性，而是控制树高，让操作稳定保持在 (O(\log n))。

BST 的一个重要训练是中序遍历：

inorder(left)
visit(root)
inorder(right)

对 BST 做中序遍历，会得到一个有序序列。这个性质经常用于验证 BST、找第 k 小元素、把树转成有序数组等问题。

11. 动态规划：把指数级枚举压成子问题复用

Lecture 10 讲 Dynamic Programming，例子是 Rod Cutting。问题是：一根长度为 (n) 的钢条，不同长度有不同价格，怎么切能收益最大？

暴力方法会枚举所有切法。长度 (n) 的钢条，在每个位置都可以切或不切，所以可能方案大约是：

$$2^{n-1}$$

动态规划的核心是最优子结构。设 (r_n) 是长度 (n) 的最大收益，则：

$$r_n=\max_{1\le i\le n}(p_i+r_{n-i})$$

含义是：第一段切出长度 (i)，收入 (p_i)，剩余长度 (n-i) 继续取最优。

递归暴力会重复计算很多子问题。DP 的关键是：

1. 定义状态：dp[n] 表示长度为 (n) 的最优收益。
2. 写转移：dp[n] = max(price[i] + dp[n-i])。
3. 确定顺序：从小长度算到大长度。
4. 保存答案：避免重复计算。

C++ 写法可以是：

int rodCutting(const vector<int>& price, int n) {
    vector<int> dp(n + 1, 0);
    for (int len = 1; len <= n; ++len) {
        for (int first = 1; first <= len; ++first) {
            dp[len] = max(dp[len], price[first] + dp[len - first]);
        }
    }
    return dp[n];
}

DP 难点通常不在代码，而在状态定义。一个实用判断是：如果问题里出现“最优”“方案数”“能否达到”，并且暴力搜索有大量重复子问题，就应该考虑 DP。

12. 贪心：每一步都选当前最好，但必须证明

Greedy Algorithms 和 DP 很像，都在做优化，但思路不同。

DP 是：

枚举子问题 -> 保存最优解 -> 组合答案

贪心是：

每一步做当前看起来最好的选择 -> 希望得到全局最优

关键区别是：贪心不是“感觉这样好”，而是要证明局部最优会导向全局最优。

活动选择问题是经典例子。给定很多活动，每个活动有开始时间和结束时间，要求选出最多个互不重叠活动。贪心策略是：

每次选择结束时间最早的活动。

为什么对？因为结束越早，留给后面的空间越大。可以用交换论证：假设某个最优解第一项不是结束最早的活动，把它替换成结束最早的活动，不会减少后续可选空间，也不会让答案变差。因此存在一个以结束最早活动开头的最优解。

贪心常见证明方法：

• Greedy choice property：存在一个最优解包含当前贪心选择。
• Exchange argument：把任意最优解改造成包含贪心选择的最优解。
• Staying ahead：证明贪心方案在每一步都不落后。

Huffman Coding 也是贪心算法的经典应用：每次合并频率最低的两个节点，最终得到最优前缀编码。

13. 图：把关系建模成节点和边

Lecture 12 讲 Graphs。图是最通用的数据结构之一：

• 社交网络：用户是节点，关注/好友是边。
• 推荐系统：用户和物品构成二分图。
• 网页网络：网页是节点，超链接是边。
• 交通网络：地点是节点，道路是边。

图可以分为：

• Directed / Undirected：有向图或无向图。
• Weighted / Unweighted：边是否有权重。
• Connected / Disconnected：是否连通。
• Cyclic / Acyclic：是否有环。

存储图常见两种方式：

1. Adjacency Matrix：用矩阵表示边，查询两点是否相连是 (O(1))，但空间是 (O(V^2))。
2. Adjacency List：每个节点保存邻居列表，空间是 (O(V+E))，更适合稀疏图。

大多数真实图是稀疏图，所以邻接表更常用。

最基础的图遍历是 BFS 和 DFS。

BFS 用队列，按层扩展，适合最短步数问题：

start -> all distance 1 nodes -> all distance 2 nodes -> ...

DFS 用递归或栈，沿着一条路径走到底，适合连通性、拓扑排序、环检测等问题。

图算法的关键不是背很多名字，而是先把问题翻译成图：

什么是节点？什么是边？边有没有方向？边有没有权重？我要求的是连通性、最短路、可达性，还是排序关系？

14. 学这门课应该怎么练

COMP2013 的内容非常适合作为算法基础训练。我的建议是按四层练：

第一层：复杂度直觉。

• 看见双重循环，能判断是否 (O(n^2))。
• 看见每次减半，想到 (O(\log n))。
• 看见分治，能写出递推式。

第二层：数据结构接口。

• 数组、链表、栈、队列分别适合什么操作。
• 哈希表为什么平均 (O(1))。
• BST 为什么取决于树高。
• 堆为什么适合 Top-K 和优先队列。

第三层：算法范式。

• 分治：拆成同类小问题。
• DP：重复子问题 + 最优子结构。
• 贪心：局部选择 + 证明。
• 图：关系建模 + 遍历。

第四层：代码实现。

• 能手写 merge sort、binary search、heapify。
• 能用 STL 写 vector、queue、stack、priority_queue、unordered_map。
• 能把伪代码翻译成 C++。
• 能处理输入输出和边界条件。

15. 面向算法实习的连接

如果目标是算法或数据方向实习，这门课的价值不只是刷题。它会影响你之后学很多东西：

• 搜索/推荐里的图结构、Top-K、哈希召回。
• 机器学习工程里的优先队列、缓存、索引。
• 大数据系统里的排序、哈希分区、图计算。
• NLP/LLM 应用里的检索、RAG 文档索引、向量召回。
• C++ 工程里的 STL 容器选择和复杂度判断。

所以这门课可以看成“工程算法语言”的底层语法。你未必每天都手写红黑树，但你需要知道为什么 map 和 unordered_map 不一样，为什么 priority_queue 能维护最大值，为什么排序后很多问题会突然简单，为什么暴力递归会爆炸，而 DP 可以把它压下来。

16. 一张总复习地图

Complexity
  -> O / Ω / Θ
  -> recursion tree
  -> master method

Divide and Conquer
  -> binary search
  -> merge sort
  -> maximum subarray

Sorting
  -> insertion sort
  -> merge sort
  -> quicksort
  -> heap sort
  -> comparison lower bound

Data Structures
  -> array / linked list
  -> stack / queue
  -> heap / priority queue
  -> hash table
  -> BST / balanced BST

Algorithm Paradigms
  -> dynamic programming
  -> greedy algorithms
  -> graph traversal

如果只记一句话，我会这样总结：

算法不是背代码模板，而是先看清问题结构，再选择一种能让操作变便宜的数据表示和求解策略。