-
정렬 알고리즘에 따른 복잡도
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 |