数据结构与算法

本文介绍数据结构与算法的基本原理（概念、复杂度、常见数据结构的原理与适用场景、算法设计思想）， 各主题的刷题模板按模块拆分在 ds/ 子目录中，见文末模块导航。

一、基本概念

• 数据结构：计算机中组织和存储数据的方式。选择合适的数据结构，直接影响算法的效率。

• 算法：解决特定问题的有限、确定、有效的操作步骤。

• 抽象数据类型（ADT）：只关心”支持哪些操作”而不关心底层实现的数据类型，如栈、队列。同一 ADT 可以有多种实现（数组或链表实现栈）。

• 刷题时通常先想清楚数据规模与操作要求，再选择数据结构与算法，最后落实到代码模板。

二、复杂度分析

2.1 时间复杂度与大 O 记号

大 O 记号描述算法运行时间随输入规模 \(n\) 增长的渐进上界：若存在正常数 \(c\) 与 \(n_0\)，使得对所有 \(n \geq n_0\) 有 \(T(n) \leq c f(n)\)，则记 \(T(n) = O(f(n))\)。

分析规则：

• 忽略常数与低阶项：\(3n^2 + 5n + 1 = O(n^2)\)；

• 顺序结构相加，循环结构相乘：两段循环嵌套为 \(O(n \cdot m)\)，先后执行为 \(O(n + m)\)；

• 只关注最坏情况或题目要求的均摊/平均情况。

常见复杂度从低到高：

\[ O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!) \]

复杂度	典型算法
\(O(1)\)	数组随机访问、哈希表查找、栈/队列进出
\(O(\log n)\)	二分查找、平衡二叉搜索树操作
\(O(n)\)	线性扫描、滑动窗口
\(O(n\log n)\)	归并排序、快速排序、堆排序
\(O(n^2)\)	冒泡/选择排序、朴素 DP、Floyd
\(O(2^n)\)	子集枚举、状压 DP
\(O(n!)\)	全排列枚举

2.2 空间复杂度

空间复杂度衡量算法运行所需的额外存储空间（不含输入本身）：

• 原地操作（如原地快排、堆排）辅助空间为 \(O(1)\)；

• 归并排序需要 \(O(n)\) 辅助数组；

• 递归算法还要计入递归调用栈深度：如快排平均 \(O(\log n)\)、最坏 \(O(n)\)。

2.3 复杂度估算技巧

刷题时根据 \(n\) 的规模反推可行算法：

• \(n \leq 20\)：可枚举子集 / 状压 DP（\(O(2^n)\)）；

• \(n \leq 500\)：\(O(n^3)\)（如 Floyd、区间 DP）；

• \(n \leq 5000\)：\(O(n^2)\)（朴素 DP、双层循环）；

• \(n \leq 10^5 \sim 10^6\)：\(O(n \log n)\) 或 \(O(n)\)（排序、二分、线性扫描、堆）。

三、常见数据结构原理

数据结构	核心原理	主要操作复杂度	典型场景
数组	连续内存，按下标随机访问	访问 \(O(1)\)；中间插入/删除 \(O(n)\)	随机访问、动态数组（vector/ArrayList）末尾追加均摊 \(O(1)\)
链表	节点 + 指针串联，非连续存储	查找 \(O(n)\)；已知位置插入/删除 \(O(1)\)	频繁增删、LRU 缓存
栈	后进先出（LIFO）	进出 \(O(1)\)	函数调用、括号匹配、单调栈（下一个更大元素）
队列	先进先出（FIFO）	进出 \(O(1)\)	BFS、任务调度；双端队列用于滑动窗口
哈希表	哈希函数映射 + 冲突解决（链地址/开放寻址）	均摊 \(O(1)\) 查找/插入/删除	去重、计数、快速查找、缓存
二叉搜索树	左小右大，中序有序	平衡时 \(O(\log n)\)，最坏 \(O(n)\)	有序集合、动态排名
堆	完全二叉树，父节点优于子节点（大/小根堆）	插入/删除 \(O(\log n)\)，取最值 \(O(1)\)	优先队列、TopK、堆排序
字典树	按字符串前缀共享节点	插入/查找 \(O(\text{长度})\)	前缀匹配、单词统计
并查集	记录元素所属集合，路径压缩 + 按秩合并	近似 \(O(\alpha(n))\)	连通性判断、Kruskal
图	顶点 + 边，邻接表 / 邻接矩阵存储	遍历 \(O(V + E)\)（邻接表）	路径、连通性、网络流

四、算法设计思想

• 枚举 / 暴力：直接尝试所有可能，适用于规模小或作为兜底思路；

• 双指针：有序数组相向/同向移动，或链表快慢指针（判环、找中点）；

• 滑动窗口：维护窗口内状态，解决子数组/子串问题（最小覆盖子串、最长无重复子串）；

• 前缀和 / 差分：\(O(1)\) 求区间和、区间增量；

• 分治：问题拆成规模更小的子问题分别解决再合并——归并排序、快速排序、二分；

• 贪心：每步取当前最优，需证明局部最优能推出全局最优（区间调度、哈夫曼编码）；

• 动态规划：适用于重叠子问题 + 最优子结构，自底向上填表，避免重复计算（背包、LIS、区间 DP）；

• 回溯：DFS 搜索所有解并剪枝，用于组合、排列、子集、N 皇后、数独等；

• 二分：在单调序列中查找，或对答案二分（最小化最大值 / 最大化最小值 / 第 K 小）；

• 位运算：\(O(1)\) 底层操作，用于优化枚举、状态压缩（状压 DP 的 mask）、按位统计贡献（拆位）；

• 图算法：BFS（最短路、层序）、DFS（连通分量、拓扑）、最短路径（Dijkstra、Bellman-Ford、Floyd）、最小生成树（Kruskal、Prim）。

五、模块导航

模块	内容	文件
刷题模板与工具函数	C++/Java 模板、类型转换、最值、运算符重载、大数计算	ds/template.md
基础数据结构	数组、字符串、链表、栈、双端队列、单调队列、单调栈、优先队列、哈希表/集合、有序表	ds/data-structures.md
滑动窗口与双指针	相向双指针、定长/不定长滑动窗口、双序列双指针	ds/sliding-window.md
前缀和与差分	一维/二维前缀和、差分数组、前缀和 + 哈希表	ds/prefix-sum.md
位运算	基础操作、异或恒等式、lowbit/置位技巧、枚举子集、拆位统计	ds/bit-manipulation.md
树与字典树	二叉树递归/前中后序/层序遍历、最大深度、对称判定、BST 操作、树状数组、字典树	ds/tree.md
回溯算法	组合、组合总和、非递减子序列、全排列、N 皇后、解数独	ds/backtracking.md
动态规划	基本思想、解题思路、0-1/完全背包、常见 DP 分类（划分/状态机/区间/树形/状压/数位等）	ds/dp.md
排序与查找	堆/归并/插入/快速/希尔排序、二分查找、二分答案、KMP	ds/sort-search.md
图论	存图方式、DFS/BFS、Bellman-Ford、Dijkstra、Floyd、并查集、生成树、拓扑排序、强连通（Kosaraju/2SAT）	ds/graph.md
线段树	单点更新 + 区间查询、懒标记区间更新	ds/segment-tree.md