以下是一份关于大O标记法（Big O Notation）的详细笔记，包括其定义、常见类型、规则，以及常见数据结构在各种操作下的时间复杂度汇总。
📘 大O标记法（Big O Notation）笔记
一、什么是大O标记法？
- 大O标记法用于描述算法在最坏情况下的时间复杂度或空间复杂度，即算法执行时间或所需空间随输入规模 $n$ 增长的渐进行为。
- 它关注的是增长趋势，忽略常数项和低阶项。
示例：
- 若某算法执行时间为 $3n^2 + 5n + 10$，则其时间复杂度为 O(n²)。
二、常见的时间复杂度（从快到慢）
| 复杂度 | 名称 | 说明 |
|---|---|---|
| O(1) | 常数时间 | 执行时间与输入规模无关 |
| O(log n) | 对数时间 | 常见于二分查找、平衡树操作 |
| O(n) | 线性时间 | 遍历整个数据结构 |
| O(n log n) | 线性对数时间 | 高效排序算法（如归并排序、快速排序平均情况） |
| O(n²) | 平方时间 | 嵌套循环，如冒泡排序 |
| O(n³) | 立方时间 | 三层嵌套循环 |
| O(2ⁿ) | 指数时间 | 如暴力解法的子集问题 |
| O(n!) | 阶乘时间 | 如旅行商问题的暴力解法 |
三、大O的简化规则
- 忽略常数项：O(5) → O(1)
- 保留最高阶项：O(n² + n) → O(n²)
- 乘法法则：嵌套循环相乘，如两层循环各 O(n) → O(n²)
- 加法法则：顺序执行取最大项，如 O(n) + O(log n) → O(n)
四、常见数据结构操作的时间复杂度汇总
注：以下假设数据结构大小为 $n$，哈希表负载因子合理，树为平衡状态（如 AVL、红黑树）。
1. 数组（Array）
| 操作 | 时间复杂度 |
|---|---|
| 索引访问（通过下标） | O(1) |
| 搜索（无序） | O(n) |
| 搜索（有序 + 二分） | O(log n) |
| 插入（末尾） | O(1)（均摊） |
| 插入（中间/开头） | O(n)（需移动元素） |
| 删除（末尾） | O(1) |
| 删除（中间/开头） | O(n) |
2. 动态数组（如 Python list、Java ArrayList）
| 操作 | 时间复杂度 |
|---|---|
| 访问 | O(1) |
| 末尾插入 | O(1) 均摊（扩容时 O(n)，但均摊后为 O(1)） |
| 中间插入/删除 | O(n) |
| 搜索 | O(n) |
3. 链表（Linked List）
| 操作 | 时间复杂度 |
|---|---|
| 访问（按索引） | O(n) |
| 搜索 | O(n) |
| 头部插入/删除 | O(1) |
| 尾部插入（无尾指针） | O(n)；有尾指针 → O(1) |
| 中间插入/删除（已知节点） | O(1)（但定位节点需 O(n)） |
双向链表（Doubly Linked List）操作复杂度类似，但支持双向遍历。
4. 栈（Stack）
| 操作 | 时间复杂度 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek/top | O(1) |
通常用数组或链表实现，均为 O(1)
5. 队列（Queue）
| 操作 | 时间复杂度 |
|---|---|
| enqueue（入队） | O(1) |
| dequeue（出队） | O(1) |
| peek | O(1) |
循环数组或链表实现，均为 O(1)
6. 哈希表（Hash Table / Dictionary / Map）
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 插入 | O(1) | O(n)（哈希冲突严重） |
| 查找 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
实际应用中通常假设为 O(1)
7. 二叉搜索树（BST）
| 操作 | 平衡 BST（如 AVL、红黑树） | 不平衡 BST（退化为链表） |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
平衡树保证 O(log n)；普通 BST 最坏为 O(n)
8. 堆（Heap，通常为二叉堆）
| 操作 | 时间复杂度 |
|---|---|
| 插入（push） | O(log n) |
| 删除最大/最小（pop） | O(log n) |
| 获取最大/最小（peek） | O(1) |
| 建堆（heapify） | O(n) |
常用于优先队列（Priority Queue）
9. 图（Graph）
- 表示方式影响复杂度：
| 表示方式 | 空间复杂度 | 遍历邻接点 | 判断边是否存在 |
|---|---|---|---|
| 邻接矩阵 | O(V²) | O(V) | O(1) |
| 邻接表 | O(V + E) | O(度(v)) | O(度(v))（需遍历） |
V = 顶点数，E = 边数
10. 字符串（String）
| 操作 | 时间复杂度 |
|---|---|
| 访问字符 | O(1) |
| 拼接（不可变字符串） | O(n + m) |
| 子串查找（朴素） | O(n·m) |
| 子串查找（KMP 等） | O(n + m) |
五、常见算法时间复杂度参考
| 算法 | 时间复杂度 |
|---|---|
| 冒泡排序、选择排序、插入排序 | O(n²) |
| 归并排序、堆排序 | O(n log n) |
| 快速排序（平均） | O(n log n)；最坏 O(n²) |
| 二分查找 | O(log n) |
| DFS / BFS（图或树） | O(V + E) |
| Dijkstra（优先队列优化） | O((V + E) log V) |
| Floyd-Warshall | O(V³) |
六、总结口诀（便于记忆）
- 数组查快改慢，链表改快查慢
- 哈希平均 O(1)，最坏退化 O(n)
- 平衡树稳 O(log n)，普通树可能变链
- 堆适合取最值，建堆只需 O(n)
- 排序最快 O(n log n)，比较排序下限
📄 版权声明
👤 作者：olis
📅 发布时间：2025年10月7日
🔗 原文链接：https://qsblog.top/%E5%A4%A7O%E6%A0%87%E8%AE%B0%E6%B3%95.html
📜 许可协议：知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
💡 转载说明：转载请注明原文出处和作者信息