[Data Structure] 자료구조별 시간복잡도
2021. 12. 31. 14:03ㆍMajor`/자료구조
| 자료구조 | 시간복잡도 | |||||||
| 평균 | 최악 | |||||||
| 접근 | 탐색 | 삽입 | 삭제 | 접근 | 탐색 | 삽입 | 삭제 | |
| Array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) - pop O(n) - remove |
O(n) | O(n) | O(1) | O(1) - pop O(n) - remove |
| Queue | O(n) | O(n) | O(1) | O(1) - dequeue O(n) - remove |
O(n) | O(n) | O(1) | O(1) - dequeue O(n) - remove |
| Deque | O(n) | O(n) | O(1) | O(1) - pop O(n) - remove |
O(n) | O(n) | O(1) | O(1) - pop O(n) - remove |
| Singly Linked List |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Doubly Linked List |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Circular Linked List |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
| Heap | O(1) - max/min |
O(1) - max/min |
O(log n) | O(log n) | O(1) - max/min |
O(1) - max/min |
O(log n) | O(log n) |
| Binary Search Tree |
O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(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) |
