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

桃扇骨 2022-09-24 04:24 145阅读 0赞

### 算法复杂度这件事 ###

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

— Eric

### 图例 ###

### 数据结构操作 ###

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">数据结构</th> 
   <th colspan="8" style="text-align:center;vertical-align:baseline;">时间复杂度</th> 
   <th style="text-align:center;vertical-align:baseline;">空间复杂度</th> 
  </tr> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">&nbsp;</th> 
   <th colspan="4" style="text-align:center;vertical-align:baseline;">平均</th> 
   <th colspan="4" style="text-align:center;vertical-align:baseline;">最差</th> 
   <th style="text-align:center;vertical-align:baseline;">最差</th> 
  </tr> 
  <tr> 
   <th style="vertical-align:baseline;">&nbsp;</th> 
   <th style="text-align:center;vertical-align:baseline;">访问</th> 
   <th style="text-align:center;vertical-align:baseline;">搜索</th> 
   <th style="text-align:center;vertical-align:baseline;">插入</th> 
   <th style="text-align:center;vertical-align:baseline;">删除</th> 
   <th style="text-align:center;vertical-align:baseline;">访问</th> 
   <th style="text-align:center;vertical-align:baseline;">搜索</th> 
   <th style="text-align:center;vertical-align:baseline;">插入</th> 
   <th style="text-align:center;vertical-align:baseline;">删除</th> 
   <th style="text-align:center;vertical-align:baseline;">&nbsp;</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Array_data_structure" rel="nofollow">Array</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29" rel="nofollow">Stack</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists" rel="nofollow">Singly-Linked List</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Doubly_linked_list" rel="nofollow">Doubly-Linked List</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Skip_list" rel="nofollow">Skip List</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Hash_table" rel="nofollow">Hash Table</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Binary_search_tree" rel="nofollow">Binary Search Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="https://en.wikipedia.org/wiki/Cartesian_tree" rel="nofollow">Cartesian Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/B_tree" rel="nofollow">B-Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Red-black_tree" rel="nofollow">Red-Black Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="https://en.wikipedia.org/wiki/Splay_tree" rel="nofollow">Splay Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow">AVL Tree</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
 </tbody> 
</table>

### 数组排序算法 ###

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">算法</th> 
   <th colspan="3" style="text-align:center;vertical-align:baseline;">时间复杂度</th> 
   <th style="text-align:center;vertical-align:baseline;">空间复杂度</th> 
  </tr> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">&nbsp;</th> 
   <th style="text-align:center;vertical-align:baseline;">最佳</th> 
   <th style="text-align:center;vertical-align:baseline;">平均</th> 
   <th style="text-align:center;vertical-align:baseline;">最差</th> 
   <th style="text-align:center;vertical-align:baseline;">最差</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow">Quicksort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Merge_sort" rel="nofollow">Mergesort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Timsort" rel="nofollow">Timsort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Heapsort" rel="nofollow">Heapsort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Bubble_sort" rel="nofollow">Bubble Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Insertion_sort" rel="nofollow">Insertion Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Selection_sort" rel="nofollow">Selection Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Shellsort" rel="nofollow">Shell Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O((nlog(n))^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O((nlog(n))^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Bucket_sort" rel="nofollow">Bucket Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n+k)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n+k)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Radix_sort" rel="nofollow">Radix Sort</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(nk)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(nk)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(nk)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n+k)</td> 
  </tr> 
 </tbody> 
</table>

### 图操作 ###

<table> 
 <tbody> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">节点 / 边界管理</th> 
   <th style="text-align:center;vertical-align:baseline;">存储</th> 
   <th style="text-align:center;vertical-align:baseline;">增加顶点</th> 
   <th style="text-align:center;vertical-align:baseline;">增加边界</th> 
   <th style="text-align:center;vertical-align:baseline;">移除顶点</th> 
   <th style="text-align:center;vertical-align:baseline;">移除边界</th> 
   <th style="text-align:center;vertical-align:baseline;">查询</th> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Adjacency_list" rel="nofollow">Adjacency list</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|+|E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| + |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Incidence_list" rel="nofollow">Incidence list</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|+|E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|E|)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">Adjacency matrix</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V|^2)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Incidence_matrix" rel="nofollow">Incidence matrix</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| ⋅ |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| ⋅ |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| ⋅ |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| ⋅ |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|V| ⋅ |E|)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(|E|)</td> 
  </tr> 
 </tbody> 
</table>

### 堆操作 ###

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">类型</th> 
   <th colspan="7" style="text-align:center;vertical-align:baseline;">时间复杂度</th> 
  </tr> 
  <tr> 
   <th style="text-align:center;vertical-align:baseline;">&nbsp;</th> 
   <th style="text-align:center;vertical-align:baseline;">HEAPIFY</th> 
   <th style="text-align:center;vertical-align:baseline;">查找最大值</th> 
   <th style="text-align:center;vertical-align:baseline;">分离最大值</th> 
   <th style="text-align:center;vertical-align:baseline;">提升键</th> 
   <th style="text-align:center;vertical-align:baseline;">插入</th> 
   <th style="text-align:center;vertical-align:baseline;">删除</th> 
   <th style="text-align:center;vertical-align:baseline;">合并</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Linked_list" rel="nofollow">Linked List (sorted)</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(m+n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Linked_list" rel="nofollow">Linked List (unsorted)</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Binary_heap" rel="nofollow">Binary Heap</a></td> 
   <td style="text-align:center;vertical-align:baseline;">O(n)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(m+n)</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Binomial_heap" rel="nofollow">Binomial Heap</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:baseline;"><a href="http://en.wikipedia.org/wiki/Fibonacci_heap" rel="nofollow">Fibonacci Heap</a></td> 
   <td style="text-align:center;vertical-align:baseline;">–</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
   <td style="text-align:center;vertical-align:baseline;">O(log(n))</td> 
   <td style="text-align:center;vertical-align:baseline;">O(1)</td> 
  </tr> 
 </tbody> 
</table>

### 大 O 复杂度图表 ###

![Big O Complexity Graph][]

Big O Complexity Graph

[Big O Complexity Graph]: http://static.webhek.com/techug-res/uploads/2016/06/123634szm02anm9jm6qqbs.png