728x90
반응형
1. 정렬 알고리즘 비교
- 대부분의 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장
- 단, 퀵 정렬은 최악의 상황의 시간 복잡도 = O(N^2)
| 정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
| 선택 정렬 | O(N^2) | O(N) | 아이디어가 매우 간단 |
| 삽입 정렬 | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때 가장 빠름 |
| 퀵 정렬 | O(NlogN) | O(N) | 대부분의 경우 가장 적합하고 빠름 |
| 계수 정렬 | O(N+K) | O(N+K) | 데이터의 크기가 한정되어 있는 경우에만 사용 가능하지만 매우 빠름 |
728x90
반응형
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 다익스트라 알고리즘 (0) | 2024.02.03 |
|---|---|
| [자료구조] DFS와 BFS (0) | 2024.02.02 |
| [자료구조] 퀵 정렬과 계수 정렬 (0) | 2024.02.01 |
| [자료구조] 선택 정렬과 삽입 정렬 (0) | 2024.01.30 |
| [자료구조] 바이너리 인덱스 트리 (Binary Indexed Tree) (2) | 2024.01.30 |