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 |