复杂度速查表
全站 92 个算法的时间/空间复杂度一页看完 · 点名称直达动画页
数据结构
| 算法 | 时间 | 空间 | 备注 |
|---|
| 数组 | O(1) | O(n) | 随机访问 O(1)；中部插删 O(n) |
| 链表 | O(n) | O(n) | 定位 O(n)；已定位处插删 O(1) |
| 栈 | O(1) | O(n) | 压栈/弹栈均摊 O(1) |
| 队列 | O(1) | O(n) | 入队/出队 O(1) |
| 树 | O(log n) | O(n) | BST 平均查改 O(log n)，退化 O(n) |
| 堆 | O(log n) | O(n) | 插入/弹顶 O(log n)，取顶 O(1) |
| 哈希表 | 期望 O(1) | O(n) | 冲突最坏 O(n) |
| 图 | O(V+E) | O(V+E) | 邻接表遍历（BFS/DFS） |
| 字典树 | O(L) | O(ΣL·Σ) | L=词长；空间随字符集放大 |
| 并查集 | 摊还 O(α(n)) | O(n) | 路径压缩 + 按秩合并，近似常数 |
| LRU 缓存 | O(1) | O(cap) | 哈希 + 双向链表 |
| 跳表 | 期望 O(log n) | O(n) | 多层索引，概率平衡 |
| 线段树 | O(log n) | O(n) | 区间查改；建树 O(n) |
| B+ 树 | O(log n) | O(n) | 高扇出、层数低——磁盘友好 |
| 布隆过滤器 | O(k) | O(m) | k 个哈希；有误报无漏报 |
| 树状数组 | O(log n) | O(n) | 前缀和查改双 log |
经典排序算法
| 算法 | 时间 | 空间 | 备注 |
|---|
| 冒泡排序 | O(n²) | O(1) | 有序提前退出最好 O(n) |
| 鸡尾酒排序 | O(n²) | O(1) | 双向冒泡，乌龟提速 |
| 双调排序 | O(n log²n) | O(1) | 排序网络，深度 O(log²n) 可并行 |
| 选择排序 | O(n²) | O(1) | 交换次数最少 O(n) |
| 插入排序 | O(n²) | O(1) | 近乎有序时接近 O(n) |
| 二分插入排序 | O(n²) | O(1) | 比较 O(n log n)，移动仍 O(n²) |
| 希尔排序 | O(n^1.3) | O(1) | 取决于步长序列 |
| 归并排序 | O(n log n) | O(n) | 稳定；自底向上迭代版 |
| 自顶向下归并 | O(n log n) | O(n) | 稳定；递归分治版 |
| 快速排序 | 平均 O(n log n) | O(log n) | 最坏 O(n²)；原地 |
| 三路快排 | 平均 O(n log n) | O(log n) | 大量重复键退化为 O(n) |
| 双轴快排 | 平均 O(n log n) | O(log n) | JDK Arrays.sort 同款 |
| 堆排序 | O(n log n) | O(1) | 原地不稳定；建堆 O(n) |
| 计数排序 | O(n+k) | O(k) | k=值域；非比较 |
| 基数排序 | O(d·(n+k)) | O(n+k) | d=位数；逐位计数排序 |
| 桶排序 | 平均 O(n) | O(n) | 均匀分布假设；桶内插排 |
动态规划
| 算法 | 时间 | 空间 | 备注 |
|---|
| 编辑距离 | O(n·m) | O(n·m) | 可滚动数组降 O(min(n,m)) |
| 0-1 背包 | O(n·W) | O(n·W) | 可滚动至 O(W)；伪多项式 |
| 完全背包 | O(n·W) | O(W) | 同行来源即可重复取 |
| 最长公共子序列 | O(n·m) | O(n·m) | 回溯恢复解需全表 |
| 最长递增子序列 | O(n²) | O(n) | 贪心+二分可 O(n log n) |
| 硬币找零方案数 | O(n·A) | O(A) | 方案数计数 DP |
| 石子合并 | O(n³) | O(n²) | 区间 DP；四边形不等式可 O(n²) |
| 旅行商 TSP | O(2ⁿ·n²) | O(2ⁿ·n) | 状压；n≈20 上限 |
| 树形 DP | O(n) | O(n) | 后序一趟 |
| 数位 DP | O(d·10) | O(d) | d=位数；含 tight 状态 |
| 换根 DP | O(n) | O(n) | 二次扫描（后序+前序） |
回溯与搜索
| 算法 | 时间 | 空间 | 备注 |
|---|
| N 皇后 | O(n!) | O(n) | 剪枝后远小于 n! |
| 子集生成 | O(2ⁿ·n) | O(n) | 枚举全部子集 |
| 全排列 | O(n!·n) | O(n) | 枚举全排列 |
| 组合总和 | O(2ⁿ) | O(n) | 和剪枝显著加速 |
| 迷宫寻路 | O(m·n) | O(m·n) | DFS 回溯找一条路 |
| 岛屿数量 | O(m·n) | O(m·n) | Flood Fill 数连通块 |
| 单词搜索 | O(m·n·4^L) | O(L) | L=词长；失配回溯 |
| 数独 | O(9^k) | O(k) | k=空格数；约束剪枝 |
| A* 寻路 | O(E log V) | O(V) | 可采纳启发式下最优 |
数学与数论
| 算法 | 时间 | 空间 | 备注 |
|---|
| 埃氏筛 | O(N log log N) | O(N) | 划倍数 |
| 线性筛 | O(N) | O(N) | 每合数只被最小质因子划一次 |
| 欧几里得算法 | O(log min(a,b)) | O(1) | 辗转相除 |
| 快速幂 | O(log n) | O(1) | 二进制取幂 |
| 扩展欧几里得 | O(log min(a,b)) | O(log n) | 回代求 Bézout 系数 |
| 中国剩余定理 | O(k log M) | O(k) | k 条同余；M=模数积 |
| 欧拉函数 | O(√n) | O(1) | 按质因子打折；筛法可批量 O(N) |
| 米勒-拉宾 | O(k log³n) | O(1) | k 轮；单轮误报 ≤1/4 |
| FFT | O(n log n) | O(n) | 蝶形网络；多项式乘法 |
| Pollard's Rho | 期望 O(n^¼) | O(1) | 生日悖论 + gcd 显影 |
计算几何
| 算法 | 时间 | 空间 | 备注 |
|---|
| 凸包 | O(n log n) | O(n) | Andrew 单调链（排序主导） |
| 旋转卡壳 | O(n) | O(1) | 凸包直径（对踵点） |
| 最近点对 | O(n log n) | O(n) | 分治 + δ 带 |
| 线段相交 | O(1) | O(1) | 跨立试验（单对判定） |
| 扫描线求交 | O((n+k) log n) | O(n) | k=交点数；扫描线 |
查找
| 算法 | 时间 | 空间 | 备注 |
|---|
| 二分查找 | O(log n) | O(1) | 前提有序 |
| 二分边界 | O(log n) | O(1) | lower/upper bound 半开区间 |
| 旋转数组搜索 | O(log n) | O(1) | 重复元素退化 O(n) |
| 二分答案 | O(log R · C) | O(1) | R=答案域；C=单次验证 |
| 三分查找 | O(log n) | O(1) | 单峰函数求极值 |
