如何分析时间复杂度和空间复杂度
# 如何分析时间复杂度和空间复杂度
# 时间复杂度
看算法执行次数随 n 的增长趋势，采用大 O 表示法。分析规则如下：
只关注循环执行次数最多的代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
常见的时间复杂度如下：
| 复杂度 | 名称 | 评级 | 典型算法 |
|---|---|---|---|
O(1) | 常数 | 🟢 极好 | 哈希表查找、数组下标访问 |
O(logn) | 对数 | 🟢 优秀 | 二分查找、平衡二叉树操作 |
O(n) | 线性 | 🟡 良好 | 线性搜索、单层遍历 |
O(nlogn) | 线性对数 | 🟡 尚可 | 归并排序、快速排序（均摊）、堆排序 |
O(n²) | 平方 | 🟠 较差 | 冒泡/选择/插入排序、双层嵌套循环 |
O(n³) | 立方 | 🔴 差 | Floyd 最短路径、矩阵乘法（朴素） |
O(2ⁿ) | 指数 | 🔴 极差 | 子集枚举、斐波那契（朴素递归） |
O(n!) | 阶乘 | 🔴 极差 | 全排列、旅行商问题（暴力） |
- 递归的时间复杂度
用递推公式分析：
斐波那契（朴素递归）：
T(n) = T(n-1) + T(n-2) + O(1)
→ 近似 O(2ⁿ) ← 指数爆炸！
归并排序：
T(n) = 2T(n/2) + O(n)
→ O(nlogn) ← 主定理
1
2
3
4
5
6
7
2
3
4
5
6
7
# 空间复杂度
看算法运行时额外占用的空间，不算输入本身，通常也用大 O。分析规则如下：
O(1)：只用了几个变量
O(n)：额外开了一个数组
O(n)：递归栈深度为 n
O(logn)：二分递归，栈深 logn
# 常见数据结构操作的时间和空间复杂度
O = 最坏不超过多少（上界）
Ω = 最好不少于多少（下界）
Θ = 就是这么多（上下界都卡死）
日常用 O 就行
| 数据结构 | 时间复杂度 | 空间复杂度 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 平均 | 最坏 | ||||||||
| 访问 | 查找 | 插入 | 删除 | 访问 | 查找 | 插入 | 删除 | 最坏 | |
| 数组 | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| 栈 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 队列 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 单向链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 双向链表 | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 跳表 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(n) | O(n) | O(n) | O(n) | O(nlogn) |
| 哈希表 | N/A | Θ(1) | Θ(1) | Θ(1) | N/A | O(n) | O(n) | O(n) | O(n) |
| 二叉搜索树 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 笛卡尔树 | N/A | Θ(logn) | Θ(logn) | Θ(logn) | N/A | O(n) | O(n) | O(n) | O(n) |
| B 树 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
| 红黑树 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
| 伸展树 | N/A | Θ(logn) | Θ(logn) | Θ(logn) | N/A | O(logn) | O(logn) | O(logn) | O(n) |
| AVL 树 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(n) |
| KD 树 | Θ(logn) | Θ(logn) | Θ(logn) | Θ(logn) | O(n) | O(n) | O(n) | O(n) | O(n) |
# 常见排序算法的时间和空间复杂度
| 算法 | 时间复杂度 | 空间复杂度 | ||
|---|---|---|---|---|
| 最好 | 平均 | 最坏 | 最坏 | |
| 快速排序 | Ω(nlogn) | Θ(nlogn) | O(n²) | O(logn) |
| 归并排序 | Ω(nlogn) | Θ(nlogn) | O(nlogn) | O(n) |
| Timsort | Ω(n) | Θ(nlogn) | O(nlogn) | O(n) |
| 堆排序 | Ω(nlogn) | Θ(nlogn) | O(nlogn) | O(1) |
| 冒泡排序 | Ω(n) | Θ(n²) | O(n²) | O(1) |
| 插入排序 | Ω(n) | Θ(n²) | O(n²) | O(1) |
| 选择排序 | Ω(n²) | Θ(n²) | O(n²) | O(1) |
| 树排序 | Ω(nlogn) | Θ(nlogn) | O(n²) | O(n) |
| 希尔排序 | Ω(nlogn) | Θ(n(logn)²) | O(n(logn)²) | O(1) |
| 桶排序 | Ω(n+k) | Θ(n+k) | O(n²) | O(n) |
| 基数排序 | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| 计数排序 | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| 立方体排序 | Ω(n) | Θ(nlogn) | O(nlogn) | O(n) |
# 常见查找算法的时间复杂度
| 算法 | 时间复杂度 |
|---|---|
| Binary Search（二分查找） | O(logn) |
| Binary Tree Traversal（二叉树遍历） | O(n) |
| Optimal Sorted Matrix Search（最优排序矩阵搜索） | O(n) |