第 14 章 数据结构与算法

第 14 章 数据结构与算法

从 Big O 记号、递归、回溯到动态规划，再到数组、链表、树、图与排序搜索，本章带你建立「写出高效代码」的核心直觉。数据结构与算法（DSA）既是工程面试的通用语言，也是把模型从「能跑」变成「跑得快、跑得稳」的底层功夫。理解了模式而非死记解法，你就能在面试官抛出任何变体时从容应对。

本章简介

数据结构与算法（data structures and algorithms，DSA）是整本教程里最贴近「写代码」的一章。前 13 章聚焦于「要算什么、在什么上算」——向量、矩阵、概率、模型、计算机与操作系统；而本章聚焦于「怎么算得对、算得快、算得优雅」。对准备 DeepMind、OpenAI 等岗位的从业者来说，DSA 扮演三重角色：其一，它是工程面试的硬通货——从两数之和到 N 皇后，绝大多数技术面都在考察你能否把现实问题剥去外壳、识别出底层的 15-20 个核心模式（双指针、滑动窗口、BFS/DFS、DP、回溯等）并快速实现；其二，它是高效实现模型的前提——知道何时用哈希表把 O(n^2) 降成 O(n)、何时用堆维护 top-k、何时用字典树加速前缀匹配，直接决定了数据管道和推理服务的真实延迟；其三，它是写出生产级代码的基础——本章反复强调的边界情况、均摊复杂度、原地 vs 额外空间的取舍，正是把「能跑的 demo」变成「经得起百万 QPS 的系统」的分水岭。

本章特别强调直觉优先、模式驱动：每个模式都从「问题的什么结构特征暗示它」「它为什么有效」「如何迁移到不同情境」三个角度讲透，而非堆砌模板。配套的 NeetCode 题目列表则用来训练你在时间压力下识别和实现这些模式的能力。

本章小节

• 基础（Foundations）：Big O 记号（增长率层级、时空复杂度分析、常见陷阱）、递归（基本情况与递归情况、信任递归、尾递归）、回溯（选择—探索—撤销三步、剪枝如何让指数算法变得可行）、动态规划（最优子结构与重叠子问题、自顶向下记忆化 vs 自底向上制表、状态定义与五步套路）——为后续所有模式提供通用语言和分析工具。
• 数组与哈希（Arrays and Hashing）：数组与动态数组的缓存局部性、字符串拼接陷阱、哈希表（哈希函数、冲突处理、装填因子、布隆过滤器），以及四大模式：哈希查找、双指针、滑动窗口、前缀和——覆盖约 40% 的面试题。
• 链表、栈与队列（Linked Lists, Stacks, and Queues）：单/双链表与哨兵节点、LIFO 栈与 FIFO 队列、单调栈（下一个更大元素、柱状图最大矩形）、优先队列与二叉堆（第 K 大、合并 K 个链表）——通过限制访问方式来简化思维的经典结构。
• 树（Trees）：二叉树四种遍历、二叉搜索树（BST 的平衡性）、字典树（前缀匹配）、并查集（Union-Find，路径压缩 + 按秩合并）、线段树与 Fenwick 树（区间查询与单点更新）——层级化数据的递归思维大全。
• 图（Graphs）：邻接表 vs 邻接矩阵、BFS（无权最短路径、多源 BFS）、DFS（环检测三态、拓扑排序 Kahn 算法）、Dijkstra 最短路径、强连通分量（Kosaraju）——关系与连接的算法模式。
• 排序与搜索（Sorting and Search）：归并/快速/计数排序与排序下界证明、二分查找（精确匹配、下界、旋转数组、对答案二分）、贪心、动态规划（爬楼梯、零钱兑换、LCS、0/1 背包）、回溯（子集、组合总和、N 皇后）——算法设计范式的大集合。

学习路径

• 前置知识：本章默认你已学完第 1-13 章，尤其是第 13 章的离散数学（命题逻辑、证明技术、集合、关系、图论、递推关系与主定理、可计算性与 P vs NP）——本章开篇对 Big O、递归和 DP 的分析会反复调用第 13 章的形式化语言；第 13 章的计算机体系结构（存储层次、缓存）解释了为什么数组比链表快 10-100 倍；第 13 章的并发与操作系统（进程、线程、调度）也为理解优先队列、消息队列与任务调度提供了背景。第 2 章矩阵和第 12 章图论则在 BST、并查集、图的邻接表示中时隐时现。
• 后续章节：本章是第 15 章生产工程的直接前置——写出高效代码、识别算法瓶颈、用合适的数据结构，是构建可靠服务的第一步，而本章的复杂度分析思维会贯穿到第 15 章的性能调优、缓存策略与系统瓶颈定位中；第 18 章 ML 系统设计会反复调用本章关于堆、哈希、图、排序与 DP 的内容来讨论召回索引、top-k 检索、调度与资源分配；即便第 16/17 章的 GPU 编程与 AI 推理，其 kernel 调度、批处理与数据布局也离不开本章培养的「时空权衡」直觉。如果你目标是工程或 infra 岗位，本章是面试的必经之路。

关键概念速览

• Big O 记号（Big O notation）：描述算法运行时间/空间随输入规模 n 的增长方式，忽略常数与低阶项；O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)，是判断「这个做法够不够快」的第一把尺子。
• 滑动窗口（sliding window）：用一左一右两个指针维护一个连续子数组/子串，在遍历中扩张与收缩；适用于「满足某约束的最长/最短子数组」，关键是约束的单调性让扩张/收缩就够了。
• 动态规划（dynamic programming，DP）：当问题具有最优子结构和重叠子问题时，把每个子问题只求解一次并缓存；核心是定义好状态 dp[i]（或 dp[i][j]）并写出状态转移方程。
• 二分查找（binary search）：在单调条件上以 O(\log n) 收敛；远不止「在有序数组里找数」，还包括找边界、旋转数组，以及「对答案二分」这种元模式。
• BFS / DFS：图的两大基本遍历——BFS 用队列逐层推进，天然给出无权图最短路径；DFS 用栈/递归一路深挖，擅长环检测、拓扑排序与回溯。
• 并查集（Union-Find，DSU）：用路径压缩 + 按秩合并把连通性查询与合并做到均摊 O(\alpha(n)) \approx O(1)，是连通分量、环检测、Kruskal 最小生成树的瑞士军刀。