每个程序员都应该收藏的算法复杂度速查表
这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。
算法 复杂度
115.197.182.80
看看
fxbszj [Firefox 47.0|Windows 7]
2016-06-20T15:37:05.000
121.22.29.121
总结的很好。
ryt [Chrome 51.0|GNU/Linux]
2016-06-21T08:37:30.000
118.198.48.102
很不错啊，总结的，点赞
AlexMahoneFBI [Maxthon 4.9|Windows 7]
2016-06-22T08:03:12.000
182.148.114.190
很好，有对比的总结，查阅一目了然！
来自四川成都的 Chrome 50.0|Windows 10 用户
2016-06-22T14:11:35.000
125.88.24.123
已收藏，方便日后查阅
Loki-A [Firefox 47.0|Windows 10]
2016-06-22T14:52:33.000
36.57.245.252
资料不错。
hello_linux [Firefox 49.0|Windows 7]
2016-07-08T14:07:14.000
58.250.181.64
我要收藏了
cicada [Chrome 54.0|Windows 7]
2016-10-30T20:54:39.000
这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 OBig-O 复杂度。
### 算法复杂度这件事


这篇文章覆盖了计算机科学里面常见算法的时间和空间的<ruby> 大 O <rp>  （ </rp> <rt>  Big-O </rt> <rp>  ） </rp></ruby> 复杂度。我之前在参加面试前，经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣，以便我在面试时不会被问住。最近这几年，我面试了几家硅谷的初创企业和一些更大一些的公司，如 Yahoo、eBay、LinkedIn 和 Google，每次我都需要准备这个，我就在问自己，“为什么没有人创建一个漂亮的大 O 速查表呢？”所以，为了节省大家的时间，我就创建了这个，希望你喜欢！


--- [Eric](https://twitter.com/ericdrowell) 


![](/data/attachment/album/201606/20/123606rd6xe34kk2xy392i.jpg)


### 图例




|  |  |  |  |  |
| --- | --- | --- | --- | --- |
| 绝佳 | 不错 | 一般 | 不佳 | 糟糕 |


### 数据结构操作




| 数据结构 | 时间复杂度 | 空间复杂度 |
| --- | --- | --- |
|  | 平均 | 最差 | 最差 |
|  | 访问 | 搜索 | 插入 | 删除 | 访问 | 搜索 | 插入 | 删除 |  |
| [Array](http://en.wikipedia.org/wiki/Array_data_structure) | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| [Stack](http://en.wikipedia.org/wiki/Stack_(abstract_data_type)) | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| [Singly-Linked List](http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists) | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| [Doubly-Linked List](http://en.wikipedia.org/wiki/Doubly_linked_list) | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| [Skip List](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Hash_table) | - | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) |
| [Binary Search Tree](http://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Cartesian_tree) | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(n) | O(n) | O(n) | O(n) |
| [B-Tree](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Splay_tree) | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| [AVL Tree](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Quicksort) | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
| [Mergesort](http://en.wikipedia.org/wiki/Merge_sort) | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| [Timsort](http://en.wikipedia.org/wiki/Timsort) | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
| [Heapsort](http://en.wikipedia.org/wiki/Heapsort) | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| [Bubble Sort](http://en.wikipedia.org/wiki/Bubble_sort) | O(n) | O(n^2) | O(n^2) | O(1) |
| [Insertion Sort](http://en.wikipedia.org/wiki/Insertion_sort) | O(n) | O(n^2) | O(n^2) | O(1) |
| [Selection Sort](http://en.wikipedia.org/wiki/Selection_sort) | O(n^2) | O(n^2) | O(n^2) | O(1) |
| [Shell Sort](http://en.wikipedia.org/wiki/Shellsort) | O(n) | O((nlog(n))^2) | O((nlog(n))^2) | O(1) |
| [Bucket Sort](http://en.wikipedia.org/wiki/Bucket_sort "Only for integers. k is a number of buckets") | O(n+k) | O(n+k) | O(n^2) | O(n) |
| [Radix Sort](http://en.wikipedia.org/wiki/Radix_sort "Constant number of digits 'k'") | O(nk) | O(nk) | O(nk) | O(n+k) |


### 图操作




| 节点 / 边界管理 | 存储 | 增加顶点 | 增加边界 | 移除顶点 | 移除边界 | 查询 |
| --- | --- | --- | --- | --- | --- | --- |
| [Adjacency list](http://en.wikipedia.org/wiki/Adjacency_list) | O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
| [Incidence list](http://en.wikipedia.org/wiki/Incidence_list) | O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |
| [Adjacency matrix](http://en.wikipedia.org/wiki/Adjacency_matrix) | O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) |
| [Incidence matrix](http://en.wikipedia.org/wiki/Incidence_matrix) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |


### 堆操作




| 类型 | 时间复杂度 |
| --- | --- |
|  | Heapify | 查找最大值 | 分离最大值 | 提升键 | 插入 | 删除 | 合并 |
| [Linked List (sorted)](http://en.wikipedia.org/wiki/Linked_list) | - | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |
| [Linked List (unsorted)](http://en.wikipedia.org/wiki/Linked_list) | - | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |
| [Binary Heap](http://en.wikipedia.org/wiki/Binary_heap) | O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) |
| [Binomial Heap](http://en.wikipedia.org/wiki/Binomial_heap) | - | O(1) | O(log(n)) | O(log(n)) | O(1) | O(log(n)) | O(log(n)) |
| [Fibonacci Heap](http://en.wikipedia.org/wiki/Fibonacci_heap) | - | O(1) | O(log(n)) | O(1) | O(1) | O(log(n)) | O(1) |


### 大 O 复杂度图表


![Big O Complexity Graph](/data/attachment/album/201606/20/123634szm02anm9jm6qqbs.png "Big O Complexity Graph")


### 推荐阅读


* [Cracking the Coding Interview: 150 Programming Questions and Solutions](http://www.amazon.com/gp/product/098478280X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=098478280X&linkCode=as2&tag=htcatu-20&linkId=B6WXIEKJHEBBWJ7B)
* [Introduction to Algorithms, 3rd Edition](http://www.amazon.com/gp/product/0262033844/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0262033844&linkCode=as2&tag=htcatu-20&linkId=J2PHCTWEAND3YQF4)
* [Data Structures and Algorithms in Java (2nd Edition)](http://www.amazon.com/gp/product/0672324539/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=0672324539&linkCode=as2&tag=htcatu-20&linkId=Y4KPAZH5PFHYXMBA)
* [High Performance JavaScript (Build Faster Web Application Interfaces)](http://www.amazon.com/gp/product/059680279X/ref=as_li_tl?ie=UTF8&camp=1789&creative=390957&creativeASIN=059680279X&linkCode=as2&tag=htcatu-20&linkId=WUNMGD5EARDJZKTT)


### 贡献者


1. [Eric Rowell](https://github.com/ericdrowell), creator of [Concrete.js](http://www.concretejs.com/), an HTML5 Canvas Framework
2. [Quentin Pleple](https://github.com/qpleple)
3. [Michael Abed](https://github.com/vault)
4. [Nick Dizazzo](https://github.com/ndizazzo)
5. [Adam Forsyth](https://github.com/agfor)
6. [David Dorfman](https://github.com/d3dave)
7. [Jay Engineer](https://github.com/jay754)
8. [Jennifer Hamon](https://github.com/jhamon)
9. [Josh Davis](https://github.com/jdavis)
10. [Nodir Turakulov](https://github.com/nodirt)
11. [Bart Massey](https://github.com/BartMassey)
12. [Vinnie Magro](https://github.com/vmagro)
13. [Miguel Amigot](https://github.com/miguel5)
14. [Drew Bailey](https://github.com/makosblade)
15. [Aneel Nazareth](https://github.com/WanderingStar)
16. [Rahul Chowdhury](https://github.com/rahulc93)
17. [Robert Burke](https://github.com/sharpobject)
18. [steven41292](https://github.com/steven41292)
19. [Brandon Amos](https://github.com/bamos)
20. [Mike Davis](https://github.com/dodgymike)
21. [Casper Van Gheluwe](https://github.com/caspervg)
22. [Joel Friedly](https://github.com/jfriedly)
23. [Oleg](https://github.com/cristaloleg)
24. [Renfred Harper](https://github.com/renfredxh)
25. [Piper Chester](https://github.com/piperchester)
26. [Eric Lefevre-Ardant](https://github.com/elefevre)
27. [Jonathan McElroy](https://github.com/jonathanmcelroy)
28. [Si Pham](https://github.com/phamtrisi)
29. [mcverry](https://github.com/mcverry)
30. [Max Hoffmann](https://github.com/mhoffman)
31. [Alejandro Ramirez](https://github.com/j4n0)
32. [Damon Davison](https://github.com/allolex)
33. [Alvin Wan](https://github.com/alvinwan)
34. [Alan Briolat](https://github.com/alanbriolat)
35. [Drew Hannay](https://github.com/drewhannay)
36. [Andrew Rasmussen](https://github.com/andyras)
37. [Dennis Tsang](https://github.com/DennisTT)
38. [Bahador Saket](https://github.com/BahadorSaket)
