2026/5/9大约 2 分钟Wiki数据结构
算法效率的两个维度：时间复杂度（运行时长）和空间复杂度（内存占用）。
Big-O 常见量级
O(1) 常数 ← 理想
O(log n) 对数 ← 优秀（二分查找）
O(n) 线性 ← 可接受
O(n log n)线性对数 ← 最优比较排序
O(n²) 平方 ← 差（冒泡排序）
O(2^n) 指数 ← 极差（暴力枚举子集）
O(n!) 阶乘 ← 最差（全排列）数据结构操作复杂度
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 顺序表 | O(1) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1)* | O(1)* |
| 栈 | O(n) | O(n) | O(1) | O(1) |
| 队列（双栈） | O(n) | O(n) | O(1) | O(1) 均摊 |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) |
| 哈希表 | — | O(1) | O(1) | O(1) |
* 表示已定位到目标节点后的操作
排序算法复杂度
| 算法 | 最佳 | 平均 | 最差 | 空间 | 稳定 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
算法的复杂度速查
| 算法 | 时间复杂度 | 空间 |
|---|---|---|
| 线性搜索 | O(n) | O(1) |
| 二分搜索 | O(log n) | O(1) |
| BFS/DFS（邻接表） | O(V+E) | O(V) |
| 迪杰斯特拉 | O((V+E) log V) | O(V) |
| 埃拉托斯特尼筛法 | O(n log log n) | O(n) |
均摊分析要点
某些操作单次可能很慢，但均摊到一系列操作上是高效的：
| 结构 | 操作 | 单次最坏 | 均摊 |
|---|---|---|---|
| 动态数组 | 插入（触发扩容） | O(n) | O(1) |
| 双栈队列 | 出队（触发倒栈） | O(n) | O(1) |
核心原理：n 次操作的总代价除以 n。