参考资源
数据结构操作复杂度速查
| 数据结构 | 插入 | 删除 | 查找 | 遍历 |
|---|---|---|---|---|
| 数组 | O(n) 中间 / O(1) 末尾 | O(n) 中间 / O(1) 末尾 | O(1) 索引 / O(n) 值 | O(n) |
| 单链表 | O(1) 头部 / O(n) 尾部 | O(1) 头部 / O(n) 指定 | O(n) | O(n) |
| 双向链表 | O(1)（已知位置） | O(1)（已知位置） | O(n) | O(n) |
| 栈 | O(1) | O(1) | — | — |
| 队列 | O(1) | O(1) | — | — |
| 优先队列（堆） | O(log n) | O(log n) | — | — |
| 二叉树（BST） | O(log n)~O(n) | O(log n)~O(n) | O(log n)~O(n) | O(n) |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | — |
| 堆 | O(log n) | O(log n) | O(1) 堆顶 | — |
| 图 | O(1) 邻接表 | O(E) | O(V+E) DFS/BFS | O(V+E) |
排序算法速查
| 算法 | 平均复杂度 | 最坏复杂度 | 空间 | 稳定 | 一句话 |
|---|---|---|---|---|---|
| 冒泡 | 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^1.3) | O(n²) | O(1) | 否 | 插入排序的改进版 |
大 O 复杂度排行
| 复杂度 | n=10 | n=1000 | n=1000000 | 评价 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 最优 |
| O(log n) | ~3 | ~10 | ~20 | 极优 |
| O(n) | 10 | 1000 | 1000000 | 可接受 |
| O(n log n) | ~30 | ~10000 | ~20000000 | 尚可 |
| O(n²) | 100 | 1000000 | 10¹² | 需警惕 |
| O(2ⁿ) | 1024 | 天文数字 | 不可能 | 不可用 |
推荐学习资源
| 类型 | 名称 | 说明 |
|---|---|---|
| 经典教材 | 《数据结构（C 语言版）》严蔚敏 | 国内高校标准教材，体系完整 |
| 经典教材 | 《算法导论》(CLRS) | 算法领域的权威参考书，深入系统 |
| 在线练习 | LeetCode (leetcode.com) | 海量算法题目，面试刷题首选 |
| 在线练习 | 牛客网 (nowcoder.com) | 国内面试练习平台，适合校招准备 |
| 可视化工具 | Visualgo (visualgo.net) | 算法可视化，帮助理解执行过程 |
| 在线编译器 | Compiler Explorer (godbolt.org) | 查看 C 代码编译后的汇编，理解底层 |