在计算机系统设计、性能调优与算法工程实践中，准确掌握算法的时空渐进复杂度（Asymptotic Complexity）与边界特性是架构选型的基石。
本速查表涵盖计算机科学 7 大工程分组、160+ 核心算法与数据结构，以高密度表格呈现其最佳时间、平均时间、最坏时间复杂度、辅助空间复杂度及核心特性（所有复杂度均为渐近上界，常数因子未计）。
🔗 相关矩阵速查：进阶高级数据结构与算法技巧速查表 · 加解密与现代密码学算法速查表 · AI 核心算法全景速查表 · Python 速查表
1. 经典与现代排序算法 (Sorting Algorithms)
按比较排序（下界 (\Omega(n \log n))）与非比较线性排序分类：
| 算法名称 (英文) | 最佳时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 核心工作机制与工程落地点 |
|---|---|---|---|---|---|---|
| 冒泡排序 (Bubble Sort) | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 | 相邻元素两两比较交换，教学基准，工业少用 |
| 选择排序 (Selection Sort) | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(1)) | 不稳定 | 每次从未排序区间选择极值，交换次数至多 (n-1) |
| 插入排序 (Insertion Sort) | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 | 小数组（(n < 32)）或基本有序数组效率极高 |
| 二分插入排序 (Binary Insertion) | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 | 二分折半查找插入位置，减少比较次数，移动仍为平方阶 |
| 希尔排序 (Shell Sort) | (O(n \log n)) | 视增量序列 | (O(n^2) \sim O(n^{1.3})) | (O(1)) | 不稳定 | 缩小增量插入排序，Hibbard / Sedgewick 增量可达亚二次方 |
| 归并排序 (Merge Sort) | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(n)) | 稳定 | 经典分治法，外排序与链表排序的标准基础 |
| 原地归并排序 (In-place Merge) | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(1)) | 稳定 | 借助块交换（Block Sort）消除辅助数组，常数较大 |
| 快速排序 (Quick Sort) | (O(n \log n)) | (O(n \log n)) | (O(n^2)) | (O(\log n)) | 不稳定 | 原地划分基准点（Pivot），三数取中/随机基准可规避最坏退化 |
| 三路快速排序 (3-Way Quick Sort) | (O(n)) | (O(n \log n)) | (O(n^2)) | (O(\log n)) | 不稳定 | 划分为小于、等于、大于三段，对海量重复键值极佳 |
| 堆排序 (Heap Sort) | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(1)) | 不稳定 | 基于完全二叉堆原地排序，最坏性能有保证但 CPU 缓存局部性差 |
| 内省排序 (Introsort) | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(\log n)) | 不稳定 | C++ std::sort 工业标准：快排 ➔ 递归过深切堆排 ➔ 小区间切插入 |
| 蒂姆排序 (TimSort) | (O(n)) | (O(n \log n)) | (O(n \log n)) | (O(n)) | 稳定 | Python list.sort / Java 工业标准：自适应识别天然有序段 (Runs) + 归并 |
| 模式击败快排 (pdqsort) | (O(n)) | (O(n \log n)) | (O(n \log n)) | (O(\log n)) | 不稳定 | Rust / Go 现代标准：对预排序、单调反序与重复元素均达到 (O(n)) |
| 计数排序 (Counting Sort) | (O(n+k)) | (O(n+k)) | (O(n+k)) | (O(k)) | 稳定 | 非比较排序，依赖数据范围 (k)，适合密集小整数 |
| 桶排序 (Bucket Sort) | (O(n+k)) | (O(n+k)) | (O(n^2)) | (O(n+k)) | 稳定 | 数据均匀分布至各桶分别排序，外部大规模排序基础 |
| 基数排序 LSD / MSD | (O(d(n+k))) | (O(d(n+k))) | (O(d(n+k))) | (O(n+k)) | 稳定 | 按有效位自低向高 (LSD) 或自顶向下 (MSD) 配合计数排序 |
| 鸽巢排序 (Pigeonhole Sort) | (O(n+k)) | (O(n+k)) | (O(n+k)) | (O(k)) | 稳定 | 键范围有限时一对一放置，计数排序的紧凑变体 |
| 鸡尾酒排序 (Cocktail Sort) | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 | 双向定向冒泡，能更快将序列末端的“乌龟”元素推向前端 |
| 梳排序 (Comb Sort) | (O(n \log n)) | (O(n^2 / 2^p)) | (O(n^2)) | (O(1)) | 不稳定 | 冒泡变体，引入递减步长跨度因子（1.3），消除末端滞后 |
| 侏儒排序 (Gnome Sort) | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 | 代码极短，类似只包含单循环的插入排序回退 |
| 圈排序 (Cycle Sort) | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(1)) | 不稳定 | 写入次数理论最少（每个元素至多写内存 2 次），适合 EEPROM/闪存 |
| 煎饼排序 (Pancake Sorting) | (O(n)) | (O(n)) | (O(n)) 翻转 | (O(1)) | 不稳定 | 仅允许前缀翻转（Prefix Reversal）操作，数学前沿问题 |
| 多路外部归并 (K-Way External) | (O(n \log k)) | (O(n \log k)) | (O(n \log k)) | (O(k)) 内存 | 稳定 | 海量数据超出内存时磁盘分块排序，败者树加速归并 |
2. 查找与选择算法 (Search & Selection)
| 算法名称 (英文) | 前提条件 | 平均时间 | 最坏时间 | 空间复杂度 | 核心特性与适用边界 |
|---|---|---|---|---|---|
| 顺序查找 (Linear Search) | 无要求 | (O(n)) | (O(n)) | (O(1)) | 任意序列，硬件缓存友好，小样本首选 |
| 二分查找 (Binary Search) | 必须单调有序 | (O(\log n)) | (O(\log n)) | (O(1)) | 经典折半，对数时间复杂度，注意中点溢出防范 |
| 插值查找 (Interpolation Search) | 均匀单调分布 | (O(\log \log n)) | (O(n)) | (O(1)) | 自适应估算步长比例，数据极度不均匀时退化为线性 |
| 指数查找 (Exponential Search) | 单调有序，未知边界 | (O(\log i)) | (O(\log i)) | (O(1)) | 先按 (2^k) 探测范围再二分，适合无限数据流或超大稀疏数组 |
| 斐波那契查找 (Fibonacci Search) | 单调有序 | (O(\log n)) | (O(\log n)) | (O(1)) | 黄金分割比例切分，全过程仅用加减法，无乘除开销 |
| 跳表查找 (Skip List Search) | 链表分层索引 | (O(\log n)) | (O(n)) | (O(n)) | 概率平衡结构，并发写入性能远超红黑树（Redis zset 核心） |
| 三分查找 (Ternary Search) | 单峰 / 单谷函数 | (O(\log n)) | (O(\log n)) | (O(1)) | 凸函数求极值，每次缩小三分之一搜索区间 |
| 哈希查找 (Hash Lookup) | 构造哈希映射表 | (O(1)) | (O(n)) | (O(n)) | 均摊常数时间，最坏取决于哈希冲突处理（拉链/开放寻址） |
| 快速选择 (Quickselect) | 无序数组求第 K 小 | (O(n)) | (O(n^2)) | (O(1)) 原地 | 基于快排分区，每轮仅递归一侧，平均线性时间（std::nth_element） |
| 中位数的中位数 (BFPRT) | 无序数组求第 K 小 | (O(n)) | (O(n)) 严格线性 | (O(\log n)) | 5 元组划分求基准点，理论最坏时间严格保障线性 |
| 内省选择 (Introselect) | 无序数组求第 K 小 | (O(n)) | (O(n \log n)) | (O(\log n)) | 工业标准：Quickselect 配合递归深限切 BFPRT / 堆排 |
3. 经典图论算法 (Graph Algorithms)
记图的顶点数为 (V)，边数为 (E)：
| 算法名称 (英文) | 求解问题目标 | 时间复杂度 | 辅助空间 | 核心约束与算法特性 |
|---|---|---|---|---|
| 广度优先搜索 (BFS) | 无权图单源最短路 / 遍历 | (O(V + E)) | (O(V)) | 队列先入先出，逐层向外扩展，天然得到无权图最短路 |
| 深度优先搜索 (DFS) | 拓扑图遍历 / 连通性 | (O(V + E)) | (O(V)) | 栈递归回溯，是 Tarjan、强连通分量与拓扑排序的核心底座 |
| 0-1 BFS | 边权仅为 0 或 1 的最短路 | (O(V + E)) | (O(V)) | 双端队列（Deque），0 权插队头，1 权插队尾，线性完成最短路 |
| Dijkstra (二叉堆优化) | 非负权图单源最短路 | (O((V + E) \log V)) | (O(V)) | 贪心松弛，严禁存在负权边；稠密图建议使用二叉堆或斐波那契堆 |
| Dijkstra (斐波那契堆) | 非负权图单源最短路 | (O(E + V \log V)) | (O(V)) | 理论界最优，但常数极大，实际工程通常使用四叉堆或二叉堆 |
| Bellman-Ford | 带负权图单源最短路 | (O(V \cdot E)) | (O(V)) | 迭代松弛 (V-1) 轮，可检测是否存在负权回路 |
| SPFA (队列优化 Bellman) | 单源最短路 / 负权检测 | 平均 (O(kE))，最坏 (O(VE)) | (O(V)) | 网格图或特定构造卡常图极易退化回 (O(VE))，非负权慎用 |
| Floyd-Warshall | 全源最短路 (APSP) | (O(V^3)) | (O(V^2)) | 动态规划三重循环，代码极简，支持负权边，矩阵表示 |
| Johnson 算法 | 稀疏带负权全源最短路 | (O(V^2 \log V + VE)) | (O(V + E)) | 结合 Bellman-Ford 势能重标号消除负权，再调用 (V) 次 Dijkstra |
| A* 启发式搜索 | 终点定向最短路径规划 | 启发函数决定 | (O(V)) | 估价函数 (f(n) = g(n) + h(n))，(h(n)) 可采纳时保证最优解 |
| Kahn 拓扑排序 | 有向无环图 (DAG) 拓扑序 | (O(V + E)) | (O(V)) | 入度统计入队法，若出队点数 (< V) 则判定图中存在有向环 |
| Kruskal (并查集) | 最小生成树 (MST) | (O(E \log E)) | (O(V)) | 边贪心排序 + 并查集判圈，极其适合稀疏图 |
| Prim (二叉堆) | 最小生成树 (MST) | (O((V + E) \log V)) | (O(V)) | 点切分定理扩展，稠密图（(E \approx V^2)）表现优异 |
| Borůvka 算法 | 最小生成树 (MST) | (O(E \log V)) | (O(V)) | 每轮各连通块独立并行找最小边，天然适合并行计算与分布式图处理 |
| Tarjan (强连通分量 SCC) | 有向图极大强连通子图 | (O(V + E)) | (O(V)) | 单次 DFS 维护时间戳 dfn 与追溯值 low，缩点建 DAG |
| Kosaraju 算法 | 有向图强连通分量 | (O(V + E)) | (O(V)) | 原图 DFS 拓扑排序后，在反向图上逆序 DFS 划分连通分量 |
| Tarjan 割点与割桥 | 无向图双连通分量 | (O(V + E)) | (O(V)) | 割点：(low[v] \ge dfn[u])；割桥：(low[v] > dfn[u]) |
| 匈牙利算法 (增广路) | 二分图最大匹配 | (O(V \cdot E)) | (O(V)) | 寻找增广路径翻转匹配边，实现简单，适合中小规模图 |
| Hopcroft-Karp | 二分图最大匹配 | (O(E \sqrt{V})) | (O(V)) | BFS 寻找最短增广路分层，DFS 多路增广，大规模二分图标准 |
| Dinic 算法 | 网络最大流 | (O(V^2 E)) (二分图 (O(E \sqrt{V}))) | (O(V + E)) | 结合残量网络 BFS 分层与当前弧优化 DFS 阻塞流，实战极快 |
| ISAP (预流推进变体) | 网络最大流 | (O(V^2 E)) | (O(V + E)) | 逆向全局标记高度标号，间隙优化（Gap Heuristic）避免无效退回 |
| Push-Relabel (最高标号) | 网络最大流 | (O(V^2 \sqrt{E})) | (O(V)) | 独立顶点推流与重标号，理论界极高，适合超稠密最大流网络 |
| MCMF (连续最短路) | 最小费用最大流 | 视最短路算法而定 | (O(V + E)) | 每次在残量网络沿费用最短路（SPFA/Primal-Dual）进行增广 |
4. 字符串匹配与文本索引 (String Algorithms)
记主串长度为 (N)，模式串长度为 (M)：
| 算法名称 (英文) | 核心解决问题 | 预处理时间/空间 | 匹配检索时间 | 算法机制与工程价值 |
|---|---|---|---|---|
| 朴素匹配 (Brute Force) | 单模式串精确匹配 | (O(1)) / (O(1)) | 平均 (O(N))，最坏 (O(NM)) | 暴力双指针，最坏退化，小字符集慎用 |
| KMP 算法 | 单模式串精确匹配 | (O(M)) / (O(M)) | (O(N)) 严格线性 | 利用前缀函数（next 数组），失配时不回溯主串指针 |
| Boyer-Moore (BM) | 现代编辑器检索首选 | (O(M + | \Sigma | )) |
| Sunday / Horspool | 高性能单模检索 | (O(M + | \Sigma | )) |
| Rabin-Karp | 滚动哈希模式匹配 | (O(M)) / (O(1)) | 平均 (O(N+M))，最坏 (O(NM)) | 针对哈希冲突进行二次比对，天然支持多模式串与二维字符矩阵匹配 |
| Z 算法 (扩展 KMP) | 匹配主串各后缀最长前缀 | (O(N+M)) | (O(N+M)) | 计算 z[i]（以 (i) 开头后缀与前缀的最长公共前缀 LCP） |
| Trie 字典树 | 字符串集合前缀检索 | 插入 (O(M)) | (O(M)) 单词长度 | 共享公共前缀，海量搜索提示、敏感词前缀过滤核心 |
| AC 自动机 (Aho-Corasick) | 多模式串同时匹配 | (O(\sum M_i)) | (O(N + \text{matches})) | Trie 树上构建类似 KMP 的失败指针（Fail Pointer），风控与敏感词过滤事实标准 |
| Manacher (马拉车) | 最长回文子串 | (O(N)) / (O(N)) | (O(N)) 线性 | 插入分隔符对齐奇偶回文，利用回文对称性加速扩张 |
| 后缀数组 (SA-IS / DC3) | 全局后缀排序与 LCP | (O(N)) / (O(N)) | (O(M \log N)) 二分 | SA-IS 算法达成严格线性时间构建，配合 Height 数组解决海量子串问题 |
| 后缀自动机 (SAM) | 识别所有子串的最小 DFA | (O(N \cdot | \Sigma | )) |
| FM 索引 (FM-Index) | 压缩全文字典检索 | 基于 BWT 变换 | (O(M)) 亚线性 | 结合 Burrows-Wheeler 变换与小波树，生物信息基因比对（Bowtie/BWA）标准 |
5. 核心数据结构基础操作 (Data Structures Complexity)
| 数据结构 (英文) | 随机访问 | 头部插入/删除 | 尾部插入/删除 | 任意搜索检索 | 核心优势与内存空间开销 |
|---|---|---|---|---|---|
| 动态数组 (Vector / ArrayList) | (O(1)) | (O(n)) | 均摊 (O(1)) | (O(n)) | 内存物理连续，CPU 缓存命中极高，尾部倍增扩容 |
| 单向 / 双向链表 (Linked List) | (O(n)) | (O(1)) | 双向且持指针 (O(1)) | (O(n)) | 节点离散分配无扩容峰值；指针域产生额外内存开销，缓存不友好 |
| 栈与队列 (Stack / Queue) | 不支持 | (O(1)) 出入 | (O(1)) 出入 | (O(n)) | 限制访问点的线性结构，LIFO（先进后出）/ FIFO（先进先出） |
| 双端队列 (Deque) | 环形数组 (O(1)) | (O(1)) | (O(1)) | (O(n)) | 两端均支持高效出入，单调队列与广义任务调度的容器 |
| 单调栈 / 单调队列 | - | - | 均摊 (O(1)) | - | 维护元素单调性，在线性 (O(n)) 时间内求解滑动窗口极值与下一个更大元素 |
| 哈希表 (Hash Table) | - | 插入均摊 (O(1)) | 删除均摊 (O(1)) | 均摊 (O(1)) | 最坏 (O(n)) 取决冲突；负载因子达到阈值需触发 Rehash 重新分配 |
| 二叉搜索树 (BST) | 不支持 | 平均 (O(\log n)) | 平均 (O(\log n)) | 最坏 (O(n)) | 未平衡时顺序插入会完全退化为单链表 |
| AVL 树 | 不支持 | 严格 (O(\log n)) | 严格 (O(\log n)) | 严格 (O(\log n)) | 严格高度平衡（左右高度差 (\le 1)），查询快，插入删除旋转频繁 |
| 红黑树 (Red-Black Tree) | 不支持 | 严格 (O(\log n)) | 严格 (O(\log n)) | 严格 (O(\log n)) | 黑色平衡，最多旋转 3 次，插入删除性能均衡（Linux 调度器、C++ std::map） |
| 伸展树 (Splay Tree) | 不支持 | 均摊 (O(\log n)) | 均摊 (O(\log n)) | 均摊 (O(\log n)) | 刚访问的节点双旋至根，自适应局部缓存强，LCT 动态树的底层基石 |
| Treap (树堆) | 不支持 | 期望 (O(\log n)) | 期望 (O(\log n)) | 期望 (O(\log n)) | 键值满足 BST、随机优先级满足二叉堆，代码极易编写，抗卡常 |
| 替罪羊树 (Scapegoat Tree) | 不支持 | 均摊 (O(\log n)) | 均摊 (O(\log n)) | 最坏 (O(\log n)) | 不用旋转，不平衡率超过阈值 (\alpha) 时直接重构整棵子树 |
| 树状数组 (Fenwick Tree / BIT) | - | 单点修改 (O(\log n)) | - | 前缀和 (O(\log n)) | 利用 lowbit(x) 树状分解，常数与代码极短，占用空间完全等同原数组 |
| 线段树 (Segment Tree) | - | 单点/区间修改 (O(\log n)) | - | 区间查询 (O(\log n)) | 借助 Lazy-Tag 支持任意结合律区间操作，空间需开 (4n) 大小 |
| 并查集 (Disjoint Set Union) | - | 合并 (\alpha(n)) | - | 查询祖先 (\alpha(n)) | 路径压缩 + 按秩合并，反阿克曼函数 (\alpha(n) \le 4)，几乎等于常数 |
| 二叉二叉堆 (Binary Heap) | 查询极值 (O(1)) | 插入 (O(\log n)) | 弹出极值 (O(\log n)) | (O(n)) | 优先队列标准实现，完全二叉树物理紧凑映射至一维数组 |
| 斐波那契堆 (Fibonacci Heap) | 查询极值 (O(1)) | 插入 (O(1)) | 弹出极值 (O(\log n)) | 减小键值 均摊 (O(1)) | 理论合并与改值最优，Dijkstra 理论加速利器 |
| 配对堆 (Pairing Heap) | 查询极值 (O(1)) | 插入 (O(1)) | 弹出极值均摊 (O(\log n)) | 合并 (O(1)) | 结构极简，实战性能显著超越斐波那契堆 |
| 可持久化线段树 (主席树) | - | 单次版本创建 (O(\log n)) | - | 历史版本查询 (O(\log n)) | 每次修改只复制改变的路径节点，空间 (O(n \log n))，区间第 K 大利器 |
6. 数论与数值计算算法 (Number Theory & Numerics)
| 算法名称 (英文) | 核心数学目标 | 时间复杂度 | 辅助空间 | 核心算法机制与应用边界 |
|---|---|---|---|---|
| 辗转相除法 (欧几里得 GCD) | 求解最大公约数 | (O(\log(\min(a, b)))) | (O(1)) | 连续取模迭代，对数级步数收敛 |
| 扩展欧几里得 (exGCD) | 求解不定方程 (ax + by = \gcd(a, b)) | (O(\log(\min(a, b)))) | (O(1)) | 递归回溯，求解乘法逆元与模线性方程的底层基座 |
| 快速幂 (Binary Exponentiation) | 快速求解 (a^b \pmod m) | (O(\log b)) | (O(1)) | 二进制拆分指数，矩阵快速幂可将递推数列（如斐波那契）加速至对数级 |
| 线性筛法 (欧拉筛) | (O(n)) 时间筛选 (1 \sim n) 内全部素数 | (O(n)) 严格线性 | (O(n)) | 保证每个合数只被其最小质因数筛除一次，同步线性计算积性函数（(\mu, \phi)） |
| 埃氏筛法 (Sieve of Eratosthenes) | 筛选区间内所有素数 | (O(n \log \log n)) | (O(n)) | 每个质数标记其倍数，存在重复标记，但实现简单 |
| Miller-Rabin 素性检验 | 概率性判断大整数是否为素数 | (O(k \log^3 n)) | (O(1)) | 基于费马小定理与二次探测定理，取前 12 个固定底数可确定性判定 (2^{64}) 内素数 |
| Pollard’s Rho 启发式分解 | 大整数质因数分解 | 期望 (O(n^{1/4})) | (O(1)) | 构造伪随机多项式序列结合 Birthday 碰撞悖论与 Floyd 判圈寻找因子 |
| 中国剩余定理 (CRT) | 求解一元模线性同余方程组 | (O(k \log m)) | (O(1)) | 模数两两互质时构造解析解；扩展 CRT (exCRT) 可利用 exGCD 处理不互质情形 |
| 快速傅里叶变换 (FFT) | (O(n \log n)) 计算多项式卷积乘法 | (O(n \log n)) | (O(n)) | 单位复数根分治折半，将传统 (O(n^2)) 卷积降至对数级，大数乘法核心 |
| 快速数论变换 (NTT) | 整数域下的多项式乘法 | (O(n \log n)) | (O(n)) | 使用原根代换单位复数根，彻底消除 FFT 的浮点数精度截断误差 |
| 高斯消元法 (Gaussian Elimination) | 求解 (n) 元一次线性方程组 | (O(n^3)) | (O(n^2)) | 矩阵初等行列变换化为上三角阶梯矩阵，结合异或运算可解模 2 异或方程组 |
7. 计算几何算法 (Computational Geometry)
| 算法名称 (英文) | 核心几何目标 | 时间复杂度 | 辅助空间 | 核心算法特性与避坑点 |
|---|---|---|---|---|
| Graham 扫描法 | 二维点集凸包构建 | (O(n \log n)) | (O(n)) | 极角排序后单调栈维护左转判定，易受共线点精度浮点误差干扰 |
| Andrew 单调链法 | 二维点集凸包构建 | (O(n \log n)) | (O(n)) | 按横纵双坐标排序，分别构建上下凸壳，常数更小、数值稳定性优于 Graham |
| 旋转卡壳 (Rotating Calipers) | 凸多边形直径 / 最小外接矩形 | (O(n)) | (O(1)) | 在已构建的凸包上逆时针平行卡尺旋转，求最远点对只需线性时间 |
| 半平面交 (Half-Plane Intersection) | 多边形核 / 凸多边形交集 | (O(n \log n)) | (O(n)) | 极角排序有向直线，双端队列维护半平面交边界，常用于可见区域计算 |
| 分治法最近点对 | 平面 (n) 个点中寻找最小距离 | (O(n \log n)) | (O(n)) | 横坐标分治，中间带区域按纵坐标排序至多考察后 6 个临近点 |
| 光线投射法 (Ray Casting) | 判定点是否在多边形内部 | (O(n)) | (O(1)) | 向任意方向发射射线，统计与多边形边界交点奇偶性（奇内偶外） |
| KD-Tree 空间近邻 | (K) 维高维空间多点检索 | 构建 (O(n \log n)) 查询期望 (O(\log n)) | (O(n)) | 交替沿各维度中位数超平面二分空间，高维空间退化，适合低维空间近邻搜索 |