# 每个程序员都应该收藏的算法复杂度速查表

+关注继续查看

--- Eric

### 图例

 绝佳 不错 一般 不佳 糟糕

### 数据结构操作

平均 最差 最差
访问 搜索 插入 删除 访问 搜索 插入 删除
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartesian Tree - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

### 数组排序算法

最佳 平均 最差 最差
Quicksort O(n log(n)) O(n log(n)) O(n^2) O(log(n))
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Timsort O(n) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Shell Sort O(n) O((nlog(n))^2) O((nlog(n))^2) O(1)
Bucket Sort O(n+k) O(n+k) O(n^2) O(n)
Radix Sort O(nk) O(nk) O(nk) O(n+k)

### 图操作

Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
Incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

### 堆操作

Heapify 查找最大值 分离最大值 提升键 插入 删除 合并
Linked List (sorted) - O(1) O(1) O(n) O(n) O(1) O(m+n)
Linked List (unsorted) - O(n) O(n) O(1) O(1) O(1) O(1)
Binary Heap O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Binomial Heap - O(1) O(log(n)) O(log(n)) O(1) O(log(n)) O(log(n))
Fibonacci Heap - O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)

### 大 O 复杂度图表

Big O Complexity Graph

3105 0

6 0

537 0

2200 0

4444 0

881 0

940 0

979 0
+关注
10077

2994

《SaaS模式云原生数据仓库应用场景实践》

《看见新力量：二》电子书