在掌握了经典算法与数据结构之后，面对海量数据极限吞吐、竞赛级多维最优化、或理论计算机科学前沿时，往往需要借助高阶紧凑数据结构、精妙分治剪枝技巧与计算复杂性下界理论。
本速查表整理了 5 大进阶与极客分组、70+ 核心高级条目，涵盖前沿数据结构、ACM/ICPC 竞赛级技巧、并行排序网络、理论计算复杂性下界猜想以及充满趣味的极客排序算法。
🔗 相关矩阵速查：算法与数据结构时空复杂度全景速查表 · 加解密与现代密码学算法速查表 · AI 核心算法全景速查表
1. 高级与紧凑前沿数据结构 (Advanced & Succinct Structures)
| 数据结构名称 (英文) | 核心操作时间复杂度 | 空间复杂度 | 数学基础与核心机制 | 典型工业与工程应用 |
|---|---|---|---|---|
| 范德姆德博阿斯树 (vEB Tree) | 所有动态前驱/后继/插入/删除 (O(\log \log U)) | (O(U)) (哈希可压至 (O(n))) | 将整数值域 (U) 递归分为高位与低位（(\sqrt{U}) 块），突破比较模型对数下界 | 极度适合固定有限小值域下的常数级动态集合优先队列 |
| 融合树 (Fusion Tree) | 静态/动态检索 (O(\log_w n)) | (O(n)) | 利用字长 (w) 的位并行算术（Word RAM），单词内并行比较多个分割键 | 打破 (O(\log n)) 下界的早期理论里程碑模型 |
| X-快速字典树 (X-fast Trie) | 查询前驱/后继 (O(\log \log U)) | (O(n \log U)) | 二叉字典树每层建立哈希表，通过层级二分搜索最高分叉点 | 指针式空间较大，是 Y-fast Trie 的理论骨架 |
| Y-快速字典树 (Y-fast Trie) | 插入/删除/查询 (O(\log \log U)) | (O(n)) 严格线性 | X-fast Trie 与平衡二叉搜索树进行微观分组聚类，空间降至线性 | 理论界的完美前驱字典，Linux 路由表理论优化模型 |
| 哈希数组映射树 (HAMT) | 查找/插入/更新 均摊 (O(1)) ((\approx \log_{32} n)) | (O(n)) 极高共享率 | 基于 Trie 树结合位图（Bitmap）压缩稀疏指针，不可变持久化数据结构首选 | Clojure / Scala / Rust 核心库不可变 Map/Set 默认底层实现 |
| 小波树 (Wavelet Tree) | 字符统计与 Rank/Select (O(\log \sigma)) | 紧凑 (O(n \log \sigma)) 位 | 字母表二分递归建立位向量，将任意字符串的查询转化为位向量的秩与选择 | 文本压缩索引、生物信息基因分析、FM 索引核心组件 |
| 软堆 (Soft Heap) | 插入/合并 (O(1))，删除极值 (O(\log(1/\epsilon))) | (O(n)) | 允许牺牲至多 (\epsilon \cdot n) 个键值的准确性（腐蚀机制），换取常数级合并 | 构造理论最优最小生成树算法（Chazelle 算法）的核心构件 |
| BK 树 (Burkhard-Keller Tree) | 模糊模糊字符串检索与编辑距离匹配 | (O(n)) | 利用度量空间的三角不等式 (|d(x, y) - d(x, z)| \le d(y, z)) 剪枝 | 拼写纠错器、相似人脸与模糊语音特征局部召回 |
| VP 树 (Vantage-Point Tree) | 度量空间高维最近邻检索 | 构建 (O(n \log n)) 查询期望 (O(\log n)) | 选择基准视点（Vantage Point），按距离中位数球面将高维空间切分为内外两部分 | 高维特征检索、图像局部特征局部检索 |
| 默克尔树 (Merkle Tree) | 包含性存在性证明验证 (O(\log n)) | (O(n)) | 叶节点存储数据哈希，非叶节点存储左右子节点哈希拼接的哈希，根即整体指纹 | 区块链 (以太坊/比特币) 状态树、Git 提交哈希链、P2P 传输去重 |
| 间隔缓冲区 (Gap Buffer) | 光标处插入/删除 (O(1)) | (O(n)) | 将动态数组未使用的空隙移动至当前文本光标位置，光标不动时操作极快 | Emacs 文本编辑器的经典核心缓冲底层实现 |
| 分段表 (Piece Table) | 任意插入/撤销 Undo (O(1) \sim O(\log n)) | 极小 (只存修改指令) | 维护原始文件缓冲区与追加缓冲区，通过片段列表描述当前视图，内存碎片极低 | VS Code (Monaco Editor) 底层大文件文本编辑核心架构 |
2. 精妙算法设计与最优化技巧 (Elegant & Contest Techniques)
| 技巧名称 (英文) | 解决问题类型 | 经典时间加速效果 | 核心数学机理与代码模式 |
|---|---|---|---|
| 李超线段树 (Li Chao Tree) | 动态插入线段，单点查询极值 | 插入线段 (O(\log^2 n)) 查询极值 (O(\log n)) | 线段树每个节点维护区间中点优势线段，下传劣势线段，优雅替代动态凸包 |
| 线段树 Beats (吉如一树) | 支持区间对 (x) 取 (\min / \max) 并求和 | 均摊 (O(n \log n)) | 维护区间最大值、次大值与最大值计数，当且仅当打到严格次大值时打 Lazy 标记 |
| 斜率优化 (Convex Hull Trick) | 动态规划状态转移方程带交叉项 (f[i] \cdot g[j]) | 从 (O(n^2)) 降至 (O(n)) 或 (O(n \log n)) | 将 DP 方程改写为截距式 (y = kx + b)，单调栈维护下凸壳，双指针或二分斜率切点 |
| WQS 二分 (外星人技巧) | 带恰好选择 (K) 个物品约束的最优化 DP | 将维度状态 (K) 降掉，加速 (\times O(\log V)) | 引入拉格朗日乘子，给每个物品施加额外惩罚/奖励斜率 (C)，二分斜率使最优解恰好选 (K) 个 |
| 树链剖分 (Heavy-Light Decomp) | 任意两点树上路径区间修改与子树统计 | 路径被切分为至多 (O(\log n)) 段重链 | 按子树大小划分为重儿子与轻儿子，重链内部 DFS 序物理连续，可无缝映射到标准线段树 |
| 树上启发式合并 (DSU on Tree) | 离线统计每棵子树内的特征分布种类 | 从暴力 (O(n^2)) 降至 (O(n \log n)) | 遍历轻儿子统计完后清空计数，遍历重儿子保留计数，重儿子贡献只计算一次 |
| 四毛子算法 (Method of Four Russians) | 在线区间最值查询 (RMQ) 严格极限 | (O(n)) 预处理，(O(1)) 查询 | 笛卡尔树转 (\pm 1) RMQ，按 (\frac{1}{2}\log n) 分块，本质不同的块至多 (2^{\text{block}}) 种，打表查表 |
| SOS 动态规划 (Sum Over Subsets) | 高维前缀和，求解所有子集属性和 | 从暴力 (O(3^n)) 降至 (O(n \cdot 2^n)) | 按二进制每一位逐维进行前缀递推，高维超立方体分步聚合 |
| 位集并行优化 (Bitset Acceleration) | 状态压缩、01 背包、有向图可达性闭包 | 获得 (1/64 \sim 1/512) 的硬件字长加速 | 使用 64 位整数字长直接执行硬件位运算（AND / OR / XOR），CPU 指令级并行 |
| 2-SAT 问题 | (n) 个布尔变量的二元析取式可满足性 | (O(V + E)) 严格线性 | 命题逻辑等价转换为有向图蕴含边（(\neg A \rightarrow B)），Tarjan 强连通分量判断 (A) 与 (\neg A) 是否在同个 SCC |
| 差分约束系统 | 求解形如 (x_i - x_j \le c) 的不等式组 | 等价于单源最短路 (O(VE)) | 移项构造最短路三角不等式 (dist[v] \le dist[u] + w)，建图跑 SPFA 判定负环 |
3. 复杂度理论下界与著名猜想 (Theoretical Lower Bounds & Conjectures)
理论计算机科学通过**条件硬度（Conditional Hardness）**与归约，证明在某些通用计算模型下不存在超越某个阈值的算法：
| 理论猜想 / 定理 (英文) | 描述的下界界限 | 适用模型 / 核心结论 | 现实技术工程指导意义 |
|---|---|---|---|
| 基于比较的排序下界 | (\Omega(n \log n)) | 决策树模型（Decision Tree Model） | 任何仅通过元素两两比对大小的排序算法，叶节点数至多 (n!)，树高至少 (\log(n!) \approx n \log n)；欲突破必须借助键值分布（基数排序） |
| 3SUM 猜想 | (\Omega(n^2)) 下界 | 给定 (n) 个整数是否存在三数和为 0 | 广泛认为不存在 (O(n^{2-\epsilon})) 算法；是数十个计算几何、动态图算法与字符串问题的下界标杆 |
| SETH 强指数时间假设 | (2^n) 下界 | 判定 (k)-SAT 问题不可在 (O((2-\epsilon)^n)) 完成 | 细粒度复杂性理论核心基石；在此假设下推导出：编辑距离（Edit Distance）严格不存在 (O(n^{2-\epsilon})) 的强次二次算法！ |
| 全源最短路 APSP 猜想 | (\Omega(n^3)) 下界 | 稠密带权有向图全源最短路 | 猜想不存在运行时间为 (O(n^{3-\epsilon})) 的真正次立方算法（Sub-cubic） |
| 矩阵乘法理论下界 | (\Omega(n^2) \le O(n^\omega)) ((\omega \approx 2.371)) | 双 (n \times n) 方阵乘法 | 暴力为 (O(n^3))，Strassen 突破至 (n^{2.807})，当前理论极限逼近 2.371，理论界长期探索是否等于 (O(n^2)) |
| 动态图连通性下界 | 每次修改/查询 (\Omega(\log n)) | 单元探测模型 (Cell-Probe) | 证明动态维护加边/删边连通性问题，不可能做到双 (O(1))，必须为树状对数开销 |
4. 排序网络与硬件并行算法 (Sorting Networks & Parallel)
在 GPU 算力卡、硬件电路 FPGA 及现代 SIMD 向量化指令集中，无分支跳转、比较步数固定的排序网络是吞吐之王：
| 网络 / 算法名称 (英文) | 比较器深度 (并行时钟) | 比较器总数 (硬件体积) | 核心运作原理与应用 |
|---|---|---|---|
| 双调排序网络 (Bitonic Sort) | (O(\log^2 n)) | (O(n \log^2 n)) | 先将序列递归构建为单峰双调序列（前半升后半降），再通过双调合并器并行折半；GPU CUDA 原生标准并行排序 |
| 奇偶归并网络 (Odd-Even Merge) | (O(\log^2 n)) | (O(n \log^2 n)) | Batcher 排序网络，利用奇数索引与偶数索引分别独立归并再两两修复交叉比较 |
| 0-1 原理 (Zero-One Principle) | - | - | 重要判定定理：如果一个由比较器构成的确定性网络能够正确排序所有由 0 和 1 组成的输入序列，则它必定能够正确排序任意实数序列 |
| 剪切排序 (Shear Sort) | (O(\sqrt{n} \log n)) | 适用于二维网格阵列 | 行蛇形升降交替排序，列自顶向下单向排序，反复迭代使得网格整体有序 |
| AKS 排序网络 | 理论深度 (O(\log n)) | (O(n \log n)) | 理论上达到严格深度下界，但因利用扩展图（Expander Graphs），常数系数高达数千万，实际工程中无法制造实现 |
5. 奇特与极客趣味排序算法 (Esoteric & Humorous Sorts)
作为计算复杂性、概率论与极客幽默的经典载体，这些算法揭示了算法设计中荒诞又严谨的极端边界：
| 算法名称 (英文) | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 荒诞又严谨的实现逻辑 |
|---|---|---|---|---|
| 猴子排序 (Bogo Sort) | (O(n \cdot n!)) | 无上限 ((\infty)) | (O(1)) | 检查数组是否有序，若无序则彻底随机洗牌（Shuffle），直到某一次洗牌碰巧有序为止（无限猴子打字机定理） |
| 慢速排序 (Slow Sort) | (O(n^{\frac{\log n}{2+\epsilon}})) | 极其极其缓慢 | (O(n)) | 践行“乘法减法法则 (Multiply and Surrender)”：递归排序前半和后半，取两半最大者放到末尾，再慢吞吞递归排序前 (n-1) 个 |
| 臭皮匠排序 (Stooge Sort) | (O(n^{\log_3 4}) \approx O(n^{2.71})) | (O(n^{2.71})) | (O(1)) | 比较首尾大小后，递归排序前 2/3、再排序后 2/3、再排序前 2/3，比经典插入排序慢得多 |
| 睡眠排序 (Sleep Sort) | (O(n + \max(A))) | 取决定时器抖动 | (O(n)) 线程 | 4chan 社区传奇：为每个数字 (x) 启动一个并发线程 sleep(x)，醒来后立即输出 (x)（将数值大小映射为时间流动） |
| 意大利面排序 (Spaghetti Sort) | 物理 (O(n)) | 物理 (O(n)) | (O(n)) | 模拟计算机硬件：将每个数字转化为长度对应的干燥意大利面条，竖直敲在桌面上，手掌从上方慢慢下压，最先碰到的面条即最大值 |
| 斯大林排序 (Stalin Sort) | (O(n)) 严格线性 | (O(n)) | (O(1)) | 铁血单遍历：任何破坏单调递增秩序的“叛逆元素”，直接予以清除销毁（Drop/Purge），剩下的必定绝对有序 |
| 奇迹排序 (Miracle Sort) | 等待宇宙奇迹 ((\infty)) | (\infty) | (O(1)) | 把数组放在内存中持续死循环检查是否有序，不进行任何修改，祈祷宇宙高能宇宙射线使内存发生微观比特翻转（Bit Flip）让它变有序 |
| 量子猴子排序 (Quantum Bogo) | 多宇宙 (O(n)) | (O(n)) | (O(1)) | 按照量子力学多世界解释（Many-Worlds）：利用量子随机源洗牌，如果在当前宇宙中数组无序，立即摧毁当前宇宙；幸存下来的宇宙里数组必定有序 |