-
分享
算法复杂度一览表
-
Hydro
SU
@
2026-5-10 17:41:53
算法复杂度一览表
探索各类算法的时间和空间复杂度，了解不同算法在执行效率和内存使用上的表现与权衡。
什么是算法复杂度？
算法复杂度是衡量算法性能的重要指标，主要包括时间复杂度（执行时间）和空间复杂度（内存使用）。复杂度通常使用大O表示法（Big O Notation）来描述算法在最坏情况下的性能上界。
时间复杂度对比
操作次数增长率：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
空间复杂度
- O(1)：常量空间复杂度，算法所需空间与输入规模无关。如简单计算、原地排序算法等。
- O(log n)：对数空间复杂度，空间需求随输入增长而缓慢增加。常见于分治算法如二分查找。
- O(n)：线性空间复杂度，空间需求与输入规模成正比。如需要额外数组的算法。
- O(n²)：平方空间复杂度，空间需求与输入规模的平方成正比。如需要二维数组的动态规划。
排序算法
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 冒泡排序 |
O(n) |
O(n²) |
O(1) |
| 选择排序 |
O(n²) |
| 插入排序 |
O(n) |
| 归并排序 |
O(n log n) |
O(n log n) |
O(n) |
| 快速排序 |
O(n²) |
O(log n) |
| 堆排序 |
O(n log n) |
O(1) |
| 计数排序 |
O(n + k) |
O(n + k) |
| 基数排序 |
O(n * k) |
| 桶排序 |
O(n) |
O(n + k) |
O(n²) |
| 希尔排序 |
O(n log n) |
O(n log² n) |
O(1) |
查找算法
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 线性查找 |
O(1) |
O(n) |
O(1) |
| 二分查找 |
O(log n) |
| 跳跃查找 |
O(√n) |
| 插值查找 |
O(log log n) |
O(n) |
| 哈希查找 |
O(1) |
O(n) |
线性数据结构
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 数组 - 访问 |
O(1) |
O(1) |
O(1) |
| 数组 - 插入 |
O(n) |
| 数组 - 删除 |
| 链表 - 访问 |
| 链表 - 插入 |
O(1) |
| 链表 - 删除 |
| 栈 - 基本操作 |
| 队列 - 基本操作 |
树形数据结构
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 二叉搜索树 - 查找 |
O(log n) |
O(log n) |
O(n) |
O(1) |
| 二叉搜索树 - 插入 |
| AVL树 - 基本操作 |
O(log n) |
O(n) |
| 红黑树 - 基本操作 |
| 堆 - 基本操作 |
O(1) |
O(1) |
| Trie树 - 基本操作 |
O(m) |
O(n*m) |
图形数据结构
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 邻接矩阵 - 访问 |
O(1) |
O(V²) |
| 邻接矩阵 - 搜索 |
| 邻接矩阵 - 插入 |
| 邻接矩阵 - 删除 |
| 邻接矩阵 - 遍历 |
O(V²) |
| 邻接表 - 访问 |
O(1) |
O(1) |
O(V) |
O(V+E) |
| 邻接表 - 搜索 |
O(V) |
| 邻接表 - 插入 |
O(1) |
| 邻接表 - 删除 |
O(E) |
| 邻接表 - 遍历 |
O(V+E) |
| 边列表 - 访问 |
O(1) |
O(E) |
O(E) |
| 边列表 - 搜索 |
| 边列表 - 插入 |
O(1) |
| 边列表 - 删除 |
| 边列表 - 遍历 |
O(E) |
| 有向图 - 基本操作 |
O(1) |
O(V+E) |
| 无向图 - 基本操作 |
| 加权图 - 基本操作 |
| 有向无环图(DAG) - 基本操作 |
哈希与映射
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 哈希表 - 基本操作 |
O(1) |
O(n) |
| 布隆过滤器 - 基本操作 |
O(k) |
O(m) |
高级数据结构
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 并查集 - 基本操作 |
O(1) |
O(α(n)) |
O(n) |
| 跳表 - 基本操作 |
O(log n) |
O(n) |
图论算法
字符串算法
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| KMP算法 |
O(n) |
O(m + n) |
O(m + n) |
O(m) |
| Rabin-Karp算法 |
O(m * n) |
O(1) |
| Boyer-Moore算法 |
O(n/m) |
O(n) |
O(m) |
数论算法
| 算法名称 |
最佳时间复杂度 ⓘ |
平均时间复杂度 ⓘ |
最差时间复杂度 ⓘ |
空间复杂度 ⓘ |
| 欧几里得算法(GCD) |
O(1) |
O(log min(a,b)) |
O(1) |
| 快速幂 |
O(log n) |
| 埃拉托斯特尼筛法 |
O(n log log n) |
O(n) |
| 模逆元计算 |
O(n³) |
O(n²) |
