정렬 알고리즘 별 시간 복잡도 정리
정렬 알고리즘에 따른 시간 복잡도Permalink
| 알고리즘 | 시간 복잡도 |
|---|---|
| 버블 정렬(Bubble Sort) | O(n2) |
| 선택 정렬(Selection Sort) | O(n2) |
| 삽입 정렬(Insertion Sort) | O(n2) |
| 퀵 정렬(Quick Sort) | O(n2) |
| 병합 정렬(Merge Sort) | O(nlogn) |
| 기수 정렬(Bubble Sort) | O(kn) k: 최대 데이터의 자릿수 |
| Arrays.sort() | O(n2) |
| Collections.sort() | O(nlogn) |
최악을 가정한 시간복잡도로, 보통 퀵 정렬이 병합 정렬보다 빠른 편이다(병합정렬이 메모리도 더 많이 잡아먹음).
시간 복잡도 문제의 일반적인 계산Permalink
보통 경우의 수가 10의 8승(108) = 1초로 잡고 문제를 풀이한다.
댓글남기기