Excellent |
Good |
Fair |
Bad |
Horrible |
| 자료구조 | 시간 복잡도 | 공간복잡도 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Average | Worst | Worst | |||||||
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | ||
| 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(n) |
| Singly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| Doubly-Linked List | O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
| 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) |
| 알고리즘 | 시간복잡도 | 공간복잡도 | ||
|---|---|---|---|---|
| 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) |
| Node / Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
|---|---|---|---|---|---|---|
| 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|) |
| Type | 시간복잡도 | ||||||
|---|---|---|---|---|---|---|---|
| Heapify | Find Max | Extract Max | Increase 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) |
| [Spring Error] No converter found for return value of type: class java.util.ArrayList (0) | 2016.11.27 |
|---|---|
| 윈도우에서 Docker로 PostgreSQL 띄우기 (0) | 2016.11.24 |
| [Redis] 레디스 데이타 타입 별 명령어 #1 - String 편 (0) | 2016.06.18 |
| [Redis] 레디스 키와 관련 명령어 (0) | 2016.06.18 |
| [Redis] 레디스 데이타 타입의 종류, 예제 및 요약 설명 (0) | 2016.06.18 |