-
정렬 알고리즘에 따른 복잡도
| Algorithms |
space complexity |
time complexity |
| 최악 |
최선 |
평균 |
최악 |
| bubble |
O(1) |
O(n) |
O(n^2) |
O(n^2) |
| heap |
O(1) |
O(n log n) |
O(n log n) |
O(log n) |
| insertion |
O(1) |
O(n n) |
O(n^2) |
O(n^2) |
| merge |
O(n) |
O(n log n) |
O(n log n) |
O(log n) |
| quick |
O(log n) |
O(n log n) |
O(n log n) |
O(n^2) |
| selection |
O(1) |
O(n^2) |
O(n^2) |
O(n^2) |
| shell |
O(1) |
O(n) |
O(n^1.25) |
O(n^1.25) |
| smooth |
O(1) |
O(n) |
O(n log n) |
O(n log n) |
자료 구조 별 시간 복잡도 Big-O
| Data Structures |
Search |
Insert |
Delete |
| Array |
O(n) |
N/A |
N/A |
| Sorted Array |
O(log n) |
O(n) |
| Linked List |
O(n) |
O(1) |
| Doubly Linked List |
| Stack |
| Hash Table |
O(n) |
| Binary Search Tree |
| B-Three |
O(log n) |
| Red-Black Tree |
| AVL Tree |