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

Bertha 。 2022-07-19 05:22 173阅读 0赞

http://www.techug.com/bigo-cheatsheet

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

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

— [Eric][]

### 图例 ###

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

<table style="border-width:1px 0px 0px 1px; border-style:solid; font-size:14px; margin:0px 0px 24px; outline:0px; padding:2px; vertical-align:baseline; border-spacing:0px; width:760px; line-height:1.28571; color:rgb(43,43,43); font-family:&quot;Microsoft YaHei&quot;,微软雅黑,&quot;Hiragino Sans GB&quot;,STHeiti,&quot;WenQuanYi Micro Hei&quot;,SimSun,sans-serif,Lucida,Verdana,serif; letter-spacing:0.5px"> 
 <thead style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 数据结构</th> 
   <th colspan="8" style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 时间复杂度</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 空间复杂度</th> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> &nbsp;</th> 
   <th colspan="4" style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 平均</th> 
   <th colspan="4" style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 最差</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 最差</th> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-transform:uppercase"> &nbsp;</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 访问</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 搜索</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 插入</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 删除</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 访问</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 搜索</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 插入</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> 删除</th> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center; text-transform:uppercase"> &nbsp;</th> 
  </tr> 
 </thead> 
 <tbody style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Array_data_structure" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Array</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Stack</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Singly-Linked List</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Doubly_linked_list" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Doubly-Linked List</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Skip_list" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Skip List</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(178,0,0); background-color:rgb(255,197,67)"> O(n log(n))</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Hash_table" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Hash Table</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(83,208,0)"> O(1)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Binary_search_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Binary Search Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="https://en.wikipedia.org/wiki/Cartesian_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Cartesian Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/B_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">B-Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/Red-black_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Red-Black Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="https://en.wikipedia.org/wiki/Splay_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">Splay Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline; text-align:center"> –</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
  <tr style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:8px; vertical-align:baseline"> <a href="http://en.wikipedia.org/wiki/AVL_tree" style="border:0px; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline; color:rgb(36,137,13)" rel="nofollow">AVL Tree</a></td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(40,101,0); background-color:rgb(200,234,0)"> O(log(n))</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:2px; vertical-align:baseline; text-align:center; color:rgb(111,110,0); background-color:rgb(255,255,0)"> O(n)</td> 
  </tr> 
 </tbody> 
</table>

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

### 图操作 ###

### 堆操作 ###

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

![Big O Complexity Graph][]

Big O Complexity Graph

### 推荐阅读 ###

*  [Cracking the Coding Interview: 150 Programming Questions and Solutions][Cracking the Coding Interview_ 150 Programming Questions and Solutions]
 *  [Introduction to Algorithms, 3rd Edition][Introduction to Algorithms_ 3rd Edition]
 *  [Data Structures and Algorithms in Java (2nd Edition)][Data Structures and Algorithms in Java _2nd Edition]
 *  [High Performance JavaScript (Build Faster Web Application Interfaces)][High Performance JavaScript _Build Faster Web Application Interfaces]

### 贡献者 ###

1.  [Eric Rowell][], creator of [Concrete.js][], an HTML5 Canvas Framework
2.  [Quentin Pleple][]
3.  [Michael Abed][]
4.  [Nick Dizazzo][]
5.  [Adam Forsyth][]
6.  [David Dorfman][]
7.  [Jay Engineer][]
8.  [Jennifer Hamon][]
9.  [Josh Davis][]
10. [Nodir Turakulov][]
11. [Bart Massey][]
12. [Vinnie Magro][]
13. [Miguel Amigot][]
14. [Drew Bailey][]
15. [Aneel Nazareth][]
16. [Rahul Chowdhury][]
17. [Robert Burke][]
18. [steven41292][]
19. [Brandon Amos][]
20. [Mike Davis][]
21. [Casper Van Gheluwe][]
22. [Joel Friedly][]
23. [Oleg][]
24. [Renfred Harper][]
25. [Piper Chester][]
26. [Eric Lefevre-Ardant][]
27. [Jonathan McElroy][]
28. [Si Pham][]
29. [mcverry][]
30. [Max Hoffmann][]
31. [Alejandro Ramirez][]
32. [Damon Davison][]
33. [Alvin Wan][]
34. [Alan Briolat][]
35. [Drew Hannay][]
36. [Andrew Rasmussen][]
37. [Dennis Tsang][]
38. [Bahador Saket][]

[Eric]: https://twitter.com/ericdrowell
[Big O Complexity Graph]: http://static.webhek.com/techug-res/uploads/2016/06/123634szm02anm9jm6qqbs.png
[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
[Eric Rowell]: https://github.com/ericdrowell
[Concrete.js]: http://www.concretejs.com/
[Quentin Pleple]: https://github.com/qpleple
[Michael Abed]: https://github.com/vault
[Nick Dizazzo]: https://github.com/ndizazzo
[Adam Forsyth]: https://github.com/agfor
[David Dorfman]: https://github.com/d3dave
[Jay Engineer]: https://github.com/jay754
[Jennifer Hamon]: https://github.com/jhamon
[Josh Davis]: https://github.com/jdavis
[Nodir Turakulov]: https://github.com/nodirt
[Bart Massey]: https://github.com/BartMassey
[Vinnie Magro]: https://github.com/vmagro
[Miguel Amigot]: https://github.com/miguel5
[Drew Bailey]: https://github.com/makosblade
[Aneel Nazareth]: https://github.com/WanderingStar
[Rahul Chowdhury]: https://github.com/rahulc93
[Robert Burke]: https://github.com/sharpobject
[steven41292]: https://github.com/steven41292
[Brandon Amos]: https://github.com/bamos
[Mike Davis]: https://github.com/dodgymike
[Casper Van Gheluwe]: https://github.com/caspervg
[Joel Friedly]: https://github.com/jfriedly
[Oleg]: https://github.com/cristaloleg
[Renfred Harper]: https://github.com/renfredxh
[Piper Chester]: https://github.com/piperchester
[Eric Lefevre-Ardant]: https://github.com/elefevre
[Jonathan McElroy]: https://github.com/jonathanmcelroy
[Si Pham]: https://github.com/phamtrisi
[mcverry]: https://github.com/mcverry
[Max Hoffmann]: https://github.com/mhoffman
[Alejandro Ramirez]: https://github.com/j4n0
[Damon Davison]: https://github.com/allolex
[Alvin Wan]: https://github.com/alvinwan
[Alan Briolat]: https://github.com/alanbriolat
[Drew Hannay]: https://github.com/drewhannay
[Andrew Rasmussen]: https://github.com/andyras
[Dennis Tsang]: https://github.com/DennisTT
[Bahador Saket]: https://github.com/BahadorSaket