目錄表
常見的資料結構與演算法複雜度
0x00 前言
記得資管資工必修的資料結構和演算法課程中，必會見到各種時間/空間複雜度的分析比較
除了考試必考之外，對於寫程式這也是有用且基本的慨念
在網路上發現對岸網友整理了一系列表格，在這邊記錄下來
0x01 圖例
| 絕佳 | 不錯 | 一般 | 不佳 | 糟糕 |
0x02 資料結構
| Data Structure | Big-O of Time | Big-O of Space | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| access | search | insert | delete | access | search | insert | delete | ||
| 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(1) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(1) |
| 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) |
0x03 排序演算法
| Algorithm | Big-O of Time | Big-O of Space | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| 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) |
0x04 Graph
| Data Structure | Store | Add Vetex | Add Edge | Remove Vetex | Remove Edge | Search |
|---|---|---|---|---|---|---|
| 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|) |
0x05 Heap
| Data Structure | Big-O of Time | ||||||
|---|---|---|---|---|---|---|---|
| Heapify | Find Max | split Max | Up Key | Insert | Delete | Merge | |
| 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) |
0x06 Big-O 曲線圖
