常用算法和數據結構的復雜度速查表，
搜索
| 算法 |
數據結構 |
時間復雜度 |
空間復雜度 |
</tr>
|
|
平均 |
最差 |
最差 |
</tr>
</thead>
| 深度優先搜索 (DFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
</tr>
| 廣度優先搜索 (BFS) |
Graph of |V| vertices and |E| edges |
- |
O(|E| + |V|) |
O(|V|) |
</tr>
| 二分查找 |
Sorted array of n elements |
O(log(n)) |
O(log(n)) |
O(1) |
</tr>
| 窮舉查找 |
Array |
O(n) |
O(n) |
O(1) |
</tr>
| 最短路徑-Dijkstra，用小根堆作為優先隊列 |
Graph with |V| vertices and |E| edges |
O((|V| + |E|) log |V|) |
O((|V| + |E|) log |V|) |
O(|V|) |
</tr>
| 最短路徑-Dijkstra，用無序數組作為優先隊列 |
Graph with |V| vertices and |E| edges |
O(|V|^2) |
O(|V|^2) |
O(|V|) |
</tr>
| 最短路徑-Bellman-Ford |
Graph with |V| vertices and |E| edges |
O(|V||E|) |
O(|V||E|) |
O(|V|) |
</tr>
</tbody>
</table>
排序
| 算法 |
數據結構 |
時間復雜度 |
最壞情況下的輔助空間復雜度 |
</tr>
|
|
最佳 |
平均 |
最差 |
最差 |
</tr>
</thead>
| 快速排序 |
數組 |
O(n log(n)) |
O(n log(n)) |
O(n^2) |
O(n) |
</tr>
| 歸并排序 |
數組 |
O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
O(n) |
</tr>
| 堆排序 |
數組 |
O(n log(n)) |
O(n log(n)) |
O(n log(n)) |
O(1) |
</tr>
| 冒泡排序 |
數組 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
</tr>
| 插入排序 |
數組 |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
</tr>
| 選擇排序 |
數組 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
</tr>
| 桶排序 |
數組 |
O(n+k) |
O(n+k) |
O(n^2) |
O(nk) |
</tr>
| 基數排序 |
數組 |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
</tr>
</tbody>
</table>
數據結構
| 數據結構 |
時間復雜度 |
空間復雜度 |
</tr>
|
平均 |
最差 |
最差 |
</tr>
|
索引 |
查找 |
插入 |
刪除 |
索引 |
查找 |
插入 |
刪除 |
|
</tr>
</thead>
| 基本數組 |
O(1) |
O(n) |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
</tr>
| 動態數組 |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
</tr>
| 單鏈表 |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
</tr>
| 雙鏈表 |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
</tr>
| 跳表 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n log(n)) |
</tr>
| 哈希表 |
- |
O(1) |
O(1) |
O(1) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
</tr>
| 二叉搜索樹 |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
</tr>
| 笛卡爾樹 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
</tr>
| B-樹 |
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) |
</tr>
| 紅黑樹 |
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) |
</tr>
| 伸展樹 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
</tr>
| AVL 樹 |
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) |
</tr>
</tbody>
</table>
堆
| Heaps |
時間復雜度 |
</tr>
|
建堆 |
查找最大值 |
提取最大值 |
Increase Key |
插入 |
刪除 |
合并 |
|
</tr>
</thead>
| 鏈表（已排序） |
- |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(m+n) |
</tr>
| 鏈表（未排序） |
- |
O(n) |
O(n) |
O(1) |
O(1) |
O(1) |
O(1) |
</tr>
| 二叉堆 |
O(n) |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
</tr>
| 二項堆 |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
</tr>
| 斐波那契堆 |
- |
O(1) |
O(log(n))* |
O(1)* |
O(1) |
O(log(n))* |
O(1) |
</tr>
</tbody>
</table>
圖
| 節點 / 邊 管理 |
Storage |
Add Vertex |
Add Edge |
Remove Vertex |
Remove Edge |
Query |
</tr>
| 鄰接表 |
O(|V|+|E|) |
O(1) |
O(1) |
O(|V| + |E|) |
O(|E|) |
O(|V|) |
</tr>
| 關聯表 |
O(|V|+|E|) |
O(1) |
O(1) |
O(|E|) |
O(|E|) |
O(|E|) |
</tr>
| 鄰接矩陣 |
O(|V|^2) |
O(|V|^2) |
O(1) |
O(|V|^2) |
O(1) |
O(1) |
</tr>
| 關聯矩陣 |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|V| ? |E|) |
O(|E|) |
</tr>
</tbody>
</table>
英文版鏈接：http://bigocheatsheet.com/
</div>
來自：http://top.jobbole.com/1599/
本文由用戶
jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
sesese色