数据结构与算法——算法视角展开

一、基础算法

1. 排序算法

比较类排序

• 基础型：冒泡排序、插入排序、选择排序、希尔排序、鸡尾酒排序、梳排序、折半插入排序。原理简单，适用于小规模或特殊场景，平均时间复杂度多为 $O(n^2)$。

• 高效型：快速排序（含双轴快排）、归并排序、堆排序、块排序 (BlockSort)、Pdqsort、GrailSort、OrsonSort。平均时间复杂度 $O(n\log n)$，是工业界标准库的主流实现，多为自适应混合排序，结合多种排序算法优势。

非比较类排序

• 核心型：计数排序、桶排序、基数排序（MSD/LSD）。基于数值范围而非比较排序，数据范围有限时可达线性复杂度。

• 优化型：基数排序 SIMD 加速、计数排序负数处理、基数排序链式实现：针对非比较排序的工程优化，提示实际性能与适用范围。

外部 / 分布式排序

• 多路归并排序、锦标赛排序、置换选择排序：处理内存无法容纳的大数据量排序，基于外存分块处理。

• MapReduce 排序、Flink 流式排序、Hive 分桶排序：分布式计算框架下的排序实现，应对海量数据场景。

2. 查找算法

基础查找

• 顺序查找、二分查找、斐波那契查找、插值查找、三分查找（单峰函数场景）：基于有序或无序序列的查找方案，二分查找是最常用的有序查找，三分查找用于单峰函数极值求解。

高级查找

• 哈希查找、跳表查找、红黑树查找、k-d 树近邻查找、插值查找边界优化：不同数据结构对应的查找方案，分别适配哈希、有序链表、平衡树、多维空间等场景。

3. 基础解题技巧

• 递归与分治、迭代、模拟：最基础的算法实现范式，分治将大问题拆分为子问题求解。

• 双指针、前缀和 / 差分、摩尔投票法、原地哈希、滑动窗口、区间合并、贪心构造：算法题中常用的技巧型方法，通过巧妙的遍历与数据组织降低时间复杂度。

二、字符串算法

1. 字符串匹配

• KMP 算法：通过前缀函数实现单模式串线性匹配，避免暴力匹配的回溯。

• Rabin-Karp 算法：基于字符串哈希的匹配算法，适合多模式匹配与长文本场景。

• BM 算法：从模式串尾部反向匹配，配合坏字符与好后缀规则，实际文本中效率高于 KMP。

• Sunday 算法：BM 的简化变体，匹配失败时关注文本下一个字符，实现简单且效率优秀。

• AC 自动机：多模式串匹配算法，基于 Trie 构建失败指针，可一次性匹配多个模式串。

• Shift-Or 算法、Two-Way 算法：两类高效单模匹配算法，前者基于位运算，后者是线性时间的最优算法之一。

• 模糊匹配（编辑距离限制）：允许一定编辑距离内的近似匹配。

2. 字符串索引相关算法

• 字典树 (Trie)：以字符为节点的前缀树，用于前缀匹配、词频统计。

• 双数组 Trie：Trie 的紧凑实现，大幅节省空间同时保持查询效率。

• 后缀自动机：状态数线性的字符串自动机，可高效处理子串计数、出现次数等问题。

• 广义后缀自动机：扩展到多个字符串的后缀自动机。

• 后缀树：基于所有后缀构建的前缀树，功能强大但空间开销大。

• 回文自动机：专门处理回文子串的自动机，可在线性时间统计所有回文子串。

3. 字符串处理与分析

• 字符串哈希：将字符串映射为哈希值，用于快速比较与匹配。

• Manacher 算法（最长回文子串）：线性时间求解字符串的最长回文子串。

• 后缀数组构建、LCP 数组构建：后缀数组将所有后缀排序，LCP 数组记录相邻后缀最长公共前缀，是字符串处理的强力工具。

• SA-IS 算法（线性后缀数组）：线性时间构建后缀数组的最优算法之一。

• 字符串最小表示法：线性时间求解字符串循环同构的最小字典序形式。

• 子串出现次数统计、字符串压缩（RLE/LZ77）：字符串的统计与压缩应用。

• 编辑距离（Levenshtein 距离、带权编辑距离）、编辑距离路径还原：衡量字符串相似度，可还原具体编辑操作。

三、图论算法

1. 图的遍历

• 深度优先搜索 (DFS)、广度优先搜索 (BFS)：图遍历的两种基础方式，是绝大多数图算法的底层框架。

• 双向 BFS：从起点与终点同时搜索，大幅缩小搜索空间，提升路径查找效率。

• 迭代加深 DFS：结合 DFS 的空间优势与 BFS 的最优性，逐步加深搜索深度。

• A \ 启发式搜索*：引入启发函数估计剩余代价，优先搜索更有希望的分支，提升路径搜索效率。

• IDA\：迭代加深与 A \ 结合，兼顾空间效率与启发式优化。

• D Lite*：动态路径规划算法，适用于环境动态变化的场景，如机器人导航。

2. 最小生成树

• Prim 算法、Kruskal 算法、Boruvka 算法：三种经典最小生成树算法，分别基于加点、加边、分治思想实现。

• 最小生成树增量更新、瓶颈生成树：扩展应用，前者处理边动态变化的场景，后者求解最大边权最小的生成树。

3. 最短路径

单源最短路径

• Dijkstra 算法（堆优化）：求解非负权图单源最短路，堆优化后复杂度 $O(m\log n)$。

• Bellman-Ford 算法：可处理负权边并检测负环，时间复杂度 $O(nm)$。

• SPFA 算法：Bellman-Ford 的队列优化版本，在稀疏图上效率更高。

• Dial 算法：针对边权为小整数的非负权图，基于桶排序实现近似线性复杂度。

多源最短路径

• Floyd-Warshall 算法：动态规划思想，可求解任意两点最短路，支持负权边，复杂度 $O(n^3)$。

• Johnson 算法：通过重赋权将负权图转化为非负权图，再多次运行 Dijkstra，适合稀疏图多源最短路。

4. 拓扑排序

• Kahn 算法、DFS 逆序法：两种求解有向无环图 (DAG) 拓扑序的经典方法，可同时检测图中是否存在环。

• 动态拓扑排序、拓扑排序环定位：扩展能力，处理边动态变化与环定位场景。

5. 关键路径

• AOE 网分析：在带权有向无环图中求解项目的最短完成工期。

• 最早 / 最晚发生时间计算、关键活动识别：通过正向递推最早时间、反向递推最晚时间，识别决定工期的关键活动。

6. 网络流

最大流算法

• Ford-Fulkerson 算法：最大流的基础思想，通过不断寻找增广路增大流量。

• Dinic 算法：基于分层图与当前弧优化的增广路算法，是工业界最常用的最大流实现。

• ISAP 算法、HLPP 最高标号预流推进：两类更高效的最大流算法，HLPP 在稠密图上优势明显。

最小割算法

• 最小割最大流定理：建立最大流与最小割的等价关系，可通过最大流求解最小割。

• 全局最小割（Stoer-Wagner 算法）：求解无向图的全局最小割。

• 割点割边（Tarjan 算法）：求解无向图的割点与桥，属于图连通性分析范畴。

费用流算法

• 最小费用最大流（SPFA+EK）：在最大流基础上优化费用，每次寻找费用最小的增广路。

• 上下界网络流、带斜率的费用流：扩展模型，处理更复杂的流量约束场景。

7. 二分图相关

• 二分图判定：通过染色法判断图是否为二分图。

• 匈牙利算法、Hopcroft-Karp 算法：求解二分图最大匹配，后者通过多路增广效率更高。

• 带权二分图匹配（KM 算法）：求解二分图最大权完美匹配。

• 二分图最大权闭合子图、最小点覆盖与最大独立集：基于二分图匹配的定理应用，可转化为网络流求解。

8. 连通性相关

• 强连通分量（Tarjan/Kosaraju/Gabow 算法）：求解有向图的强连通分量，Tarjan 基于一次 DFS 实现，应用最广。

• 缩点重构 DAG：将强连通分量缩为单点，把原图转化为 DAG 以简化问题。

• 2-SAT 问题：布尔可满足性问题的特例，可通过强连通分量高效求解。

• 双连通分量（点 / 边）：求解无向图的点双连通与边双连通分量。

• 动态连通性、k – 连通性、边连通度计算：连通性的扩展问题，处理动态图与连通度度量。

9. 特殊图算法

• DAG 最长路径：在有向无环图上基于拓扑序求解最长路径。

• 树的重心、树的直径：树的两个核心属性，分别对应删除后子树最大规模最小的节点、树上最远两点距离。

• LCA（最近公共祖先）倍增 / 树链剖分实现：求解树上两点最近公共祖先的经典算法，倍增易实现，树链剖分查询更快且可结合其他树操作。

四、数学与计算几何算法

1. 数论算法

基础数论

• 最大公约数 (GCD)/ 最小公倍数 (LCM)：数论基础运算，求解两整数的最大公共约数与最小公共倍数，核心通过辗转相除法实现。

• 扩展欧几里得算法：在求解 GCD 的同时算出贝祖等式的整数解，是求解模逆元、线性同余方程的核心工具。

• 贝祖定理：线性不定方程 ax+by=c 有整数解的充要条件是 gcd(a,b) 整除 c；且一定存在整数解使得 ax+by=gcd(a,b)，是数论方程求解的理论基础。

素数相关

• 素数判定（米勒 – 拉宾算法）：概率性素性测试算法，通过多轮基测试可在极低错误率下快速判定大数素性，是大数素性判断的工业标准。

• 埃氏筛 / 线性筛 / 区间筛：批量生成素数的三类算法；埃氏筛原理简单，线性筛（欧拉筛）保证每个合数仅被筛一次，达到线性复杂度；区间筛用于求解大数值区间内的素数。

• 质因数分解（Pollard-Rho 算法）：基于随机化与生日悖论的大数分解算法，期望时间复杂度约为 $O(n^{1/4})$，可快速找到合数的非平凡因子，是大数质因数分解的核心方案。

幂运算与模运算

• 快速幂：通过二进制拆分指数，将幂运算从 $O(n)$ 优化至 $O(\log n)$，几乎所有模运算场景都会配合使用。

• 矩阵快速幂：将快速幂思想扩展到矩阵运算，用于加速线性递推数列（如斐波那契）的求解。

• 快速乘：模拟二进制拆分乘法，避免大数相乘时的数值溢出，适用于大模数场景。

• 模逆元：模运算中的 “除法等价操作”，常用于分数取模，可通过扩展欧几里得算法或费马小定理求解。

• 中国剩余定理：求解一元线性同余方程组，给出模数互质场景下的通解公式。

• 模线性方程求解：求解形如 $ax \equiv b \pmod{m}$ 的同余方程，基于扩展欧几里得算法实现。

• 高次同余方程（BSGS 算法）：全称 Baby-Step Giant-Step（大步小步算法），用于求解离散对数问题 $a^x \equiv b \pmod{p}$，时间复杂度 $O(\sqrt{p})$。

2. 组合数学算法

• 排列组合计算：基础计数工具，求解有序排列与无序组合的方案数。

• 卡特兰数应用：经典组合数列，可用于括号匹配、二叉树结构计数、凸多边形三角划分等场景。

• 卢卡斯定理：用于大组合数对小质数取模，将大组合数拆解为小组合数的乘积取模。

• 容斥原理：通过 “加加减减” 对重叠集合计数去重，是处理多约束组合计数的核心方法。

• 斯特林数（第一 / 第二类）：第一类描述将 n 个元素排成 k 个轮换的方案数；第二类描述将 n 个元素划分为 k 个非空集合的方案数。

• 贝尔数：n 个元素的集合划分总方案数，等于第二类斯特林数的前缀和。

• 组合数递推与预处理：通过杨辉三角递推或阶乘 + 逆元打表，实现组合数的快速查询。

3. 计算几何算法

基础几何计算

• 点线面关系判定、向量叉积 / 点积：计算几何底层工具；点积用于计算投影、夹角，叉积用于判断转向、面积与线段位置关系。

• 点到直线距离、线段相交判定：基于向量运算的基础几何判定，是复杂几何算法的底层支撑。

核心算法

• 凸包算法（Graham 扫描 / Andrew 算法）：求解平面点集的最小凸多边形；Graham 基于极角排序扫描，Andrew 按坐标双端扫描，实现更稳定。

• 三维凸包：将凸包问题扩展到三维空间，求解空间点集的最小凸多面体。

• 最近点对（分治算法）：采用分治思想拆分点集后合并求解，时间复杂度 $O(n\log n)$。

• 旋转卡壳（最远点对）：用一对平行线 “卡住” 凸包并旋转，可在线性时间内求解凸包直径（最远点对）、宽度、最小外接矩形等几何属性。

扩展算法

• 多边形凹凸性判断：基于顶点叉积符号的一致性，判断多边形是否为凸多边形。

• 平面点集 Voronoi 图：将平面划分为多个区域，每个区域内的点到对应种子点距离最近，广泛应用于地理、图形学领域。

五、策略算法

1. 动态规划

核心类型

• 线性 DP：状态沿线性结构转移，是动态规划最基础的形式，典型如背包、序列问题。

• 区间 DP：以区间为状态单位，通过小区间合并求解大区间问题，如石子合并、回文子串计数。

• 树形 DP：在树结构上进行状态转移，通常通过后序遍历自底向上计算。

• 状态压缩 DP：用二进制表示集合状态，处理小规模集合的选排问题。

• 数位 DP：针对数字位数设计状态，常用于求解满足特定约束的数字计数问题。

• 概率 DP：状态转移附带概率，用于求解随机过程中的期望、概率问题。

• 博弈论 DP（Nim 游戏）：基于博弈状态转移求解胜负态，Nim 游戏是其经典模型。

• 插头 DP（网格问题）：高级状压 DP，通过轮廓线与插头记录连通性，求解网格上的回路、路径覆盖等复杂连通性问题。

• 基环树 DP：针对带一个环的树（基环树）的动态规划，通常先断环成树再处理。

• 换根 DP：通过两次遍历实现树上所有节点作为根的答案求解，避免重复计算。

优化技巧

• 状态压缩：用二进制等紧凑形式表示状态，压缩状态空间。

• 单调队列优化：维护单调队列快速求解滑动窗口最值，优化一类 DP 转移。

• 斜率优化：将转移方程转化为斜率形式，用凸包维护最优决策点。

• 四边形不等式优化：利用决策单调性，将区间 DP 从 $O(n^3)$ 降至 $O(n^2)$。

• 滚动数组：仅保留相邻状态，大幅降低空间复杂度。

• 决策单调性优化：利用最优决策点的单调性，减少转移枚举量。

• 矩阵快速幂优化线性 DP：将线性递推 DP 转化为矩阵幂运算，加速大步数求解。

• 前缀和优化多维 DP：通过前缀和快速计算区间和，优化求和类转移。

经典问题

• 背包系列：包含 0-1 背包、完全背包、多重背包、分组背包、二维费用背包、有依赖的背包等，是动态规划的经典模型族。

• 序列问题：包括最长公共子序列 (LCS)、最长上升子序列 (LIS)、编辑距离、最长回文子序列、最长公共子串、最大子段和等经典线性 DP 问题。

2. 贪心算法

核心应用场景

• 活动选择、霍夫曼编码、最小生成树（Prim/Kruskal）、分数背包、区间覆盖、带截止时间的任务调度，均为贪心算法的经典应用，通过每一步选择局部最优推导全局最优。

关键支撑

• 贪心选择性质：全局最优可通过一系列局部最优选择得到；最优子结构：问题最优解包含子问题最优解。二者是贪心算法正确性的必要条件，需通过证明或反例构造验证适用性。

3. 回溯与剪枝

经典问题

• 组合排列、N 皇后、数独求解、子集生成、单词搜索、正则表达式匹配、括号生成、岛屿数量，均为深度优先搜索 + 回溯试错的典型场景，通过枚举所有可能并回退状态求解。

优化技巧

• 可行性剪枝：提前排除不可能得到解的分支；最优性剪枝：当前分支已无法优于已知最优解时提前终止；另有记忆化回溯、双向回溯、剪枝顺序优化等手段，用于压缩搜索空间。

4. 分支限界

• 优先队列分支限界：以广度优先为基础，用优先队列按代价排序拓展节点，优先搜索更优分支。

• 动态界值更新：实时更新上下界，提升剪枝效率。

• 典型应用：TSP 问题求解、0-1 背包优化，用于求解组合优化问题的精确最优解。

5. 随机化算法

• 随机快速排序：随机选取基准元素，消除最坏输入场景，平均时间复杂度稳定在 $O(n\log n)$。

• 蒙特卡洛算法：运行时间固定，结果以一定概率正确，适用于可容忍小概率错误的场景。

• 拉斯维加斯算法：结果必定正确，运行时间随机，不断重试直到得到正确解。

• 舍伍德算法：通过随机化消除输入的最坏情况，保证算法平均性能稳定。

六、工程化算法优化技巧

1. 性能优化相关算法

• 内存对齐优化、缓存局部性优化、向量化编程（SIMD/AVX）、批量操作优化、延迟计算、写时复制 (COW)、零拷贝技术、预取优化：从硬件特性、内存访问、计算模式等维度提升程序运行效率，是工业级代码性能优化的核心手段。

• 复杂度分析（时间 / 空间）：评估算法资源消耗的基础方法；Amdahl 定律：计算并行系统的理论加速比上限，指导并行优化方向。

2. 并发与分布式算法

• 无锁算法、分段锁 / 细粒度锁、乐观锁 / 悲观锁选型：不同粒度的并发控制方案，平衡并发性能与数据一致性。

• 分布式一致性算法（Raft/Paxos）：解决分布式系统多节点数据一致性问题，Raft 更易工程实现。

• 分布式锁（Redis/ZooKeeper）：分布式环境下实现互斥访问的通用方案。

• 数据分片与负载均衡算法：将数据与流量均匀分配到多节点，提升系统吞吐量与扩展性。

七、前沿领域算法

1. 人工智能相关算法

• 卷积层张量运算算法：卷积神经网络核心，通过卷积核提取空间特征，广泛用于计算机视觉。

• 循环层序列处理算法：循环神经网络核心，通过门控机制处理序列依赖，用于自然语言、时序数据。

• Transformer 注意力机制算法：通过自注意力机制并行处理长序列，是当前大语言模型的核心架构。

• 强化学习经验回放算法、优先级经验回放算法：通过存储并重放历史经验提升样本利用率，优先级回放优先采样高价值经验。

2. 机器学习基础算法

监督学习算法

• 线性回归、逻辑回归：基础线性模型，分别用于回归与二分类任务。

• 支持向量机 (SVM)：通过最大化分类间隔构建分类器，适用于小样本高维场景。

• 决策树与随机森林：决策树基于特征分裂做决策，随机森林是多棵决策树的 Bagging 集成。

• K – 近邻算法 (KNN)：基于邻居样本投票做分类 / 回归，属于惰性学习算法。

• 朴素贝叶斯：基于贝叶斯定理与特征独立假设的概率分类器，计算高效。

• 梯度提升树 (GBDT/XGBoost)：Boosting 集成算法，通过迭代拟合残差提升模型精度，是表格数据建模的主流方案。

• 集成学习（Bagging/Boosting）：两类集成范式，Bagging 通过并行训练多个基模型投票，Boosting 通过串行迭代逐步优化。

无监督学习算法

• K – 均值聚类、层次聚类：经典聚类算法，分别基于质心迭代与层次合并划分样本。

• 主成分分析 (PCA)：线性降维算法，通过正交变换保留最大方差信息。

• DBSCAN 密度聚类：基于密度可达性聚类，可发现任意形状簇并识别噪声点。

• 孤立森林：基于孤立路径长度检测异常样本，适用于异常检测场景。

• 谱聚类：基于图论谱理论的聚类算法，对非凸分布数据效果较好。

• EM 算法（高斯混合模型）：迭代求解含隐变量模型的参数，高斯混合模型是其典型应用。

搜索与优化算法

• 遗传算法、模拟退火、粒子群优化 (PSO)、蚁群算法：均为启发式优化算法，模拟自然 / 生物行为，在复杂、非凸的优化问题中寻找近似最优解，如蚁群算法常用于 TSP 问题优化。

3. 区块链相关算法

• 共识算法（PoW/PoS/PBFT/DPoS）：区块链节点达成数据一致性的核心机制，分别基于工作量、权益、拜占庭容错等原理设计。

• 默克尔树验证算法：通过哈希树结构快速验证数据完整性与存在性，是区块链数据结构的核心。

• 分布式哈希表 (DHT) 算法：分布式节点存储与寻址方案，无需中心节点即可定位数据。

• IPFS 内容寻址算法：基于内容哈希而非地址定位文件，实现分布式文件存储与传输。

4. 量子计算相关算法

• 量子傅里叶变换：量子版本的快速傅里叶变换，是众多量子算法的基础组件。

• Grover 搜索算法：实现无序数据库的二次加速搜索，时间复杂度 $O(\sqrt{n})$。

• Shor 算法（大数分解）：可在多项式时间内完成大数质因数分解，对传统 RSA 加密体系构成挑战。