常见算法的空间复杂度和时间复杂度
以下是常见算法的时间复杂度和空间复杂度总结，按算法类型分类，并附典型示例：
一、排序算法
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(n²) | O(1) | 否 |
| 插入排序 | O(n²) | O(n²) | O(1) | 是 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 是 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | 是 |
| 基数排序 | O(n × k) | O(n × k) | O(n + k) | 是 |
注：
k表示数据的范围（如计数排序中最大最小值差）。- 快速排序的最坏情况（已排序数组）可通过随机化避免。
二、搜索算法
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 线性搜索 | O(n) | O(1) | 无序数据 |
| 二分查找 | O(log n) | O(1) | 有序数组 |
| 哈希表查找 | O(1) | O(n) | 无冲突的理想情况 |
| DFS/BFS | O(V + E) | O(V) | 图/树遍历 |
注：
V为顶点数，E为边数（图算法中）。- 哈希表查找的复杂度假设哈希函数均匀分布。
三、图算法
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| Dijkstra | O((V+E) log V) | O(V) | 无负权边的最短路径 |
| Bellman-Ford | O(V×E) | O(V) | 可处理负权边 |
| Floyd-Warshall | O(V³) | O(V²) | 多源最短路径 |
| Prim | O(E log V) | O(V) | 最小生成树（MST） |
| Kruskal | O(E log E) | O(E) | 最小生成树 |
| 拓扑排序 | O(V + E) | O(V) | 有向无环图（DAG） |
注：
- Dijkstra 使用优先队列优化后的复杂度。
- Kruskal 的复杂度基于并查集（Union-Find）优化。
四、动态规划（DP）
| 问题 | 时间复杂度 | 空间复杂度 | 示例 |
|---|---|---|---|
| 斐波那契数列 | O(n) | O(1) | dp[i] = dp[i-1] + dp[i-2] |
| 0-1背包问题 | O(n×W) | O(W) | dp[i][w] = max(val[i] + dp[i-1][w-wt[i]], dp[i-1][w]) |
| 最长公共子序列 | O(m×n) | O(m×n) | LCS（二维DP表） |
| 矩阵链乘法 | O(n³) | O(n²) | 最优括号化方案 |
注：
W表示背包容量，n为物品数量。- 空间复杂度可通过滚动数组优化（如斐波那契数列用两个变量代替数组）。
五、字符串算法
| 算法 | 时间复杂度 | 空间复杂度 | 用途 |
|---|---|---|---|
| KMP算法 | O(m + n) | O(m) | 字符串匹配 |
| Rabin-Karp | O(m + n) | O(1) | 哈希滚动匹配 |
| Trie树 | O(L) | O(L×N) | 前缀匹配（L为单词长度，N为节点数） |
| Manacher | O(n) | O(n) | 最长回文子串 |
六、递归与分治
| 算法 | 时间复杂度 | 空间复杂度 | 示例 |
|---|---|---|---|
| 汉诺塔问题 | O(2ⁿ) | O(n) | 递归调用栈深度 |
| 归并排序 | O(n log n) | O(n) | 分治思想 |
| 快速幂 | O(log n) | O(1) | a^n的计算优化 |
七、其他重要算法
| 算法 | 时间复杂度 | 空间复杂度 | 应用场景 |
|---|---|---|---|
| 并查集（路径压缩） | O(α(n)) | O(n) | 连通性检测（α为反阿克曼函数） |
| 欧拉筛法 | O(n) | O(n) | 素数筛选 |
| FFT（快速傅里叶变换） | O(n log n) | O(n) | 信号处理/多项式乘法 |
总结对比
| 复杂度级别 | 典型算法 | 适用场景 |
|---|---|---|
| O(1) | 哈希表访问 | 高频查询 |
| O(log n) | 二分查找、堆操作 | 有序数据操作 |
| O(n) | 线性搜索、计数排序 | 小规模数据处理 |
| O(n log n) | 快速排序、归并排序 | 大规模排序 |
| O(n²) | 冒泡排序、Floyd-Warshall | 小规模计算 |
| O(2ⁿ)/O(n!) | 回溯、暴力穷举 | 极小规模组合问题 |
总结
- 排序算法：快速排序、归并排序、堆排序是
O(n log n)的“三巨头”。 - 图算法：Dijkstra 和 Prim 用优先队列优化，复杂度含
log V。 - 动态规划：空间复杂度常可优化（如滚动数组）。
- 递归算法：注意栈空间（如汉诺塔的
O(n)空间）。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 qyhome！
相关推荐
2025-05-29
C++实现十大排序算法
以下是 C++ 实现的十大排序算法 及其详细介绍，包括
时间复杂度、空间复杂度、稳定性、适用场景 等。
1. 冒泡排序（Bubble
Sort）
思想：重复比较相邻元素，如果顺序错误就交换，直到没有交换发生。
特点：简单但效率低，适合小规模数据。
void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; }...
2025-06-02
每周LeetCode回顾-1
456.
132模式
思路：
从后往前遍历，维护一个单调递减的栈，同时使用
k 记录所有出栈元素的最大值。
class Solution {public: bool find132pattern(vector<int>& nums) { // 获取数组大小 int n = nums.size(); // 单调栈 stack<int> stk; // 存储 k int k = INT_MIN; // 利用单调栈使得一直满足 j < k for(int i = n-1; i >= 0; --i) { // 发现 k > i 的情况直接返回 true if(k > nums[i]) return true; while(!stk.empty() && stk.top()...
2025-06-23
每周LeetCode回顾-2
633.
平方数之和
思路：双指针
对于给定的非负整数 \(c\)，需要判断是否存在整数 \(a\) 和 \(b\)，使得 \(a^2+b^2=c\)。可以枚举 \(a\) 和 \(b\) 所有可能的情况，时间复杂度为 \(O(c^2)\)。但是暴力枚举有一些情况是没有必要的。例如：当
\(c=20\) 时，当 \(a=1\) 的时候，枚举 \(b\) 的时候，只需要枚举到 \(b=5\) 就可以结束了，这是因为 \(1^2+5^2=25>20\)。当 \(b>5\) 时，一定有 \(1^2+b^2>20\)。
假设 \(a\leq b\)，初始时 \(a=0\)，\(b=\sqrt
c\)，进行如下操作：
如果 \(a^2+b^2=c\)，我们找到了题目要求的一个解，直接返回
true；
如果 \(a^2+b^2<c\)，此时需要将
\(a\) 的值加 \(1\)，继续查找；
如果 \(a^2+b^2>c\)，此时需要将
\(b\) 的值减 \(1\)，继续查找。
当...
2025-06-09
C++中常用的数学函数
在C++中，常用的数学函数主要通过 <cmath>
头文件提供（C++中也可用
<math.h>，但推荐使用C++风格的头文件）。以下是一些常用的数学函数及其说明：
1. 基本运算
函数
描述
示例
abs(x)
绝对值（整数，<cstdlib>）
abs(-5) →
5
fabs(x)
浮点数的绝对值
fabs(-3.14) →
3.14
fmod(x, y)
浮点数取余
fmod(10.5, 3.0) →
1.5
remainder(x, y)
带符号的余数（IEEE规范）
remainder(10.5, 3.0) →
-0.5
fmax(x, y)
返回最大值
fmax(2.0, 3.0) →
3.0
fmin(x, y)
返回最小值
fmin(2.0, 3.0) →
2.0
2....
2025-06-06
C++中sort函数的详细使用指南
C++ sort
算法的详细使用指南
sort 是 C++ STL 中最常用的排序算法，定义在
<algorithm>
头文件中。它使用高效的排序算法（通常是快速排序的变体）对序列进行排序。
基本用法
1. 默认排序（升序）
#include <algorithm>#include <vector>#include <iostream>int main() { std::vector<int> nums = {4, 2, 5, 3, 1}; // 默认升序排序 std::sort(nums.begin(), nums.end()); for (int num : nums) { std::cout << num << " "; } // 输出: 1 2 3 4 5}
2. 降序排序
#include...
2025-07-18
C++20的ranges::命名空间
在 C++20 中，<algorithm>头文件中的许多算法被引入了
std::ranges命名空间，这些算法支持范围（Range）概念，提供了更现代、更安全的接口。以下是
C++20 std::ranges中主要的算法分类和示例：
1.
不修改序列的算法（Non-modifying）
查找类：
ranges::find/ ranges::find_if/
ranges::find_if_not
ranges::find_first_of
ranges::adjacent_find
ranges::search/ ranges::search_n
ranges::find_end
ranges::binary_search（需范围有序）
ranges::lower_bound/ ranges::upper_bound/
ranges::equal_range（需范围有序）
计数类：
ranges::count/...