算法分析与设计

Appearance

第2章 数据结构：从接口到缓存 ​

第一章解决的是一个前置问题：写代码之前，你到底在解决什么问题？

第二章接着问：

问题看清楚之后，数据应该怎样组织，算法才跑得动？

这就是数据结构的任务。

很多初学者以为数据结构是在背名字：数组、链表、栈、队列、哈希表、树、堆。实际上，更重要的问题是：

text
我要频繁做哪些操作？
这些操作的规模有多大？
哪些操作必须快？
我愿意付出多少额外空间和实现复杂度？

数据结构不是"装数据的容器"，而是一组操作契约。同一批数据，换一种组织方式，查找、插入、删除、取最值、按顺序遍历的成本就会完全不同。

为什么 agent 时代更需要懂数据结构 ​

Coding agent 很擅长根据一句话生成代码。问题是，它经常会生成能跑但结构不合适的代码。

例如：

python
def has_duplicate(names):
    seen = []
    for name in names:
        if name in seen:
            return True
        seen.append(name)
    return False

这段代码看起来很自然，也能通过小测试。但 name in seen 会在线性列表里逐个查找。最坏情况下，第 1 次查 0 个，第 2 次查 1 个，第 3 次查 2 个，总代价接近：

text
0 + 1 + 2 + ... + (n - 1) = Θ(n²)

如果改用集合：

python
def has_duplicate(names):
    seen = set()
    for name in names:
        if name in seen:
            return True
        seen.add(name)
    return False

查找和插入通常就是常数级别，整体变成 Θ(n)。

这不是语法差异，而是数据结构差异。你不懂数据结构，就很难发现 agent 把一个本该线性的任务写成了平方级。

数据结构选择从操作需求开始：同一批数据，因为高频操作不同，会走向不同组织方式
数据结构选择从操作需求开始：同一批数据，因为高频操作不同，会走向不同组织方式

本章主线 ​

本章会像普通算法教材一样讲清楚数据结构本身：

  • 抽象数据类型和操作接口
  • 数组、动态数组、链表、栈、队列
  • 集合、字典和哈希表
  • 树、有序结构、优先队列、堆和并查集
  • 摊还分析
  • 接口、缓存与 agent 时代的数据结构审查

但讲完概念不是终点。每个知识点都会回到一个现实动作：

当 agent 给出代码或推荐数据结构时，你如何判断它选得对不对？

你会反复练习一张数据结构选择卡：

text
任务：
数据规模：
高频操作：
- 操作 A：频率 / 是否要求快
- 操作 B：频率 / 是否要求快

候选数据结构：
选择理由：
放弃其他结构的理由：
时间复杂度：
空间复杂度：
需要 agent 帮什么：
我必须自己审查什么：

这张卡是第二章的核心工具。它能把"帮我写个功能"改写成 agent 更容易执行、人也更容易审查的规格。

贯穿案例：在线课堂互动系统 ​

为了让本章不变成一串孤立名词，我们会反复回到同一个现实任务：

设计一个在线课堂互动系统。学生可以进入课堂、提交问题、撤回最近一次提交；老师可以按提交顺序查看问题，也可以优先处理被标记为紧急的问题；系统还要统计每个学生提交了多少问题，并在课后导出记录。

这个系统看起来是一个产品功能，其实包含了很多数据结构问题：

子需求结构信号本章会用到
保存课堂中的学生判断是否已经加入set
按学生 id 找学生信息key-value 查询dict
保存所有问题记录按顺序追加和导出list
撤回最近一次提交后进先出栈
按提交顺序处理普通问题先进先出队列
优先处理紧急问题反复取最高优先级堆
按时间段导出记录范围查询有序结构
临时分组讨论合并集合、判断是否同组并查集
问题不断增长一串追加的总成本摊还分析
反复读取上下文复用已计算状态缓存

接下来每一节都会拿其中一块来拆。读的时候你可以不断问：

text
如果我只让 agent 直接写代码，它可能会怎么写？
这个写法在哪个操作上会慢？
我现在学到的数据结构能解决哪个瓶颈？

这样，数据结构就不再是抽象表格，而是你解决现实功能时的工具箱。

本章的专业读法 ​

读数据结构时，不要只问"它是什么"，而要沿着六个层次读：

层次要问的问题产出
接口它向外承诺哪些操作？ADT 或 API
表示它内部怎样组织数据？数组、节点、哈希桶、树形关系
不变量什么性质必须一直成立？左小右大、堆序、先进先出
成本每个操作随规模怎样增长？时间复杂度、空间复杂度
适用边界什么需求下它好，什么需求下它差？选择理由和放弃理由
审查问题Agent 可能在哪里选错或说错？反例、追问、改写提示词

这六层会贯穿本章。比如讲堆时，不只是会用 heapq，还要知道堆的不变量是什么、为什么 heappop 是 O(log n)、为什么它适合反复取最小值、不适合完整排序。讲哈希表时，不只是会用 dict，还要知道 key 必须可哈希、冲突如何影响期望复杂度、为什么范围查询不是它的强项。

这也是 agent 时代学习数据结构的方式：你不一定要手写所有底层代码，但必须能审查接口是否符合需求、复杂度分析是否准确、实现是否维护了不变量。

本章各节 ​

本章学习目标 ​

学完本章，你应该能：

  • 用操作接口描述一个数据结构，而不是只背它的名字
  • 说清 Python 中常见结构的典型复杂度
  • 识别列表查找、头部删除、重复排序等隐藏成本
  • 根据操作频率选择数组、链表、栈、队列、集合、字典、树、堆或并查集
  • 区分最坏情况、期望情况和摊还情况
  • 用缓存视角理解数据结构接口、Skill、memoization 与 KV-cache
  • 审查 agent 给出的数据结构推荐，并写出接受或拒绝的理由

上一章：第1章 当你让 AI 帮你写代码时，你还需要懂算法吗？

下一节：2.1 抽象数据类型与操作契约

新时代的算法课程