跳转至

⚡ 复杂度速查表

面试必背。重点是:为什么是这个复杂度,能现场推导。

常用数据结构操作复杂度(平均)

数据结构 查找 插入 删除 备注
数组(按索引) O(1) O(n) O(n) 顺序访问快
有序数组(二分) O(log n) O(n) O(n) 插入/删除要移动
链表 O(n) O(1)* O(1)* *已知节点位置时
双向链表 O(n) O(1) O(1) LRU 的基础
栈 / 队列 O(1)(顶/端) O(1) O(1) —
哈希表 O(1) O(1) O(1) 最坏 O(n)(冲突)
二叉搜索树(平衡) O(log n) O(log n) O(log n) AVL/红黑树
堆 O(1) 取最值 O(log n) O(log n) Top-K 神器
并查集 ≈O(α(n)) — — α(n) 近似常数
Trie O(len) O(len) O(len) 字符串前缀查询

排序算法对比

算法 平均 最坏 空间 稳定性 备注
冒泡排序 O(n²) O(n²) O(1) 稳定 实际不用
选择排序 O(n²) O(n²) O(1) 不稳定 交换次数少
插入排序 O(n²) O(n²) O(1) 稳定 近乎有序时快
希尔排序 O(n^1.3) O(n²) O(1) 不稳定 插入排序改进
归并排序 O(n log n) O(n log n) O(n) 稳定 外部排序基础
快速排序 O(n log n) O(n²) O(log n) 不稳定 随机 pivot 规避最坏
堆排序 O(n log n) O(n log n) O(1) 不稳定 原地 Top-K
计数排序 O(n+k) O(n+k) O(k) 稳定 值域小
桶排序 O(n) O(n²) O(n) 稳定 分布均匀时
基数排序 O(d·(n+k)) O(d·(n+k)) O(n+k) 稳定 按位排

背口诀:快排不稳、堆排不稳、选择不稳;归并稳定但空间 O(n);希尔/快排/堆排平均都是 O(n log n)。

常见算法复杂度

算法 时间复杂度 说明
二分查找 O(log n) 有序数组
DFS / BFS(图) O(V + E) 邻接表
Dijkstra O((V+E) log V) 堆优化
Floyd O(V³) 全源最短路
Kruskal O(E log E) 并查集
Prim O(E log V) 堆优化
快排分治 / 归并 O(n log n) —
DP(背包) O(n·W) 伪多项式
回溯(全排列) O(n!) 剪枝可优化

复杂度增长对比(n = 10⁶ 时)

O(1)      < 10⁻⁹ s 级       常数
O(log n)  ≈ 20 步            二分
O(n)      ≈ 1e6 步           一次扫描
O(n log n)≈ 2e7 步           排序
O(n²)     ≈ 1e12 步          勉强(10⁴ 上限)
O(2ⁿ)     ≈ 天文数字         n 上限 ~25
O(n!)     ≈ 更夸张           n 上限 ~10

刷题自查

  • [ ] 能背出表并解释"为什么归并稳定而快排不稳定"
  • [ ] 能推导二分、快排、堆排的复杂度
  • [ ] 看到题能 30 秒内判断数据规模 → 允许的复杂度 → 该用哪个算法

教程来源:Akun-python/autumn-recruitment。 MIT 许可证全文。