javascript_algorithm / 정렬 알고리즘 / 3.5 Big O of Sorting Algorithm
3.5Big O of Sorting Algorithm
기본 정렬 알고리즘들의 시간 복잡도 및 공간 복잡도
추억의 쪽지 시험
기본 정렬 알고리즘들의 Big O
Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬), Selection Sort(선택 정렬)은 기본적인 정렬 알고리즘들로, 시간 복잡도가 O(n²)이기 때문에 Quadratic Sort라고도 불린다.
| 알고리즘 | 시간 복잡도(Best) | 시간 복잡도(Average) | 시간 복잡도(Worst) | 공간 복잡도 |
|---|---|---|---|---|
| 버블 정렬 | O(n) | O(n²) | O(n²) | O(1) |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) |
이 방법들은 정렬 방식이 다르지만, 대체로 시간이 많이 걸리는 편이다.
다음 포스팅보다는 보다 빠른 정렬 알고리즘들에 대해 알아보자.
- Merge Sort
- Quick Sort
- Radix Sort
이 정렬 알고리즘들은 앞서 본 기본 정렬 알고리즘들보다 훨씬 빠르지만(O(n log n)), 공간 복잡도가 늘어난다.