6.6 정렬 문제의 하한
시간복잡도의 하한은 어떠한 알고리즘도 문제의 하한보다 빠르게 해를 구할 수 없음을 의미
문제의 하한 : 적어도 시간복잡도만큼 시간이 걸린다는 뜻
n개의 서로 다른 숫자를 비교정렬하는 결정트리의 높이가 비교정렬의 하한이 된다.
결정트리의 높이를 계산하기 위해서 'k개의 이파리가 있는 이진트리의 높이는 logk보다 크다'라는 특성 이용
n!개의 leaf를 가진 결정트리의 높이 > log(n!)
log(n!) = O(nlogn) 이므로 비교정렬의 하한은 O(nlogn)
O(nlogn)보다 빠른 시간복잡도를 가진 비교정렬의 알고리즘은 없어
==> 비교정렬의 하한은 Ω(nlogn)
6.7 기수 정렬
✔️ 기수 정렬의 정의
: 범위 내에 있는 숫자에 대해 각 자릿수별로 정렬하는 알고리즘
✔️ 안정성을 가진다
: 입력에 중복된 숫자가 있을 때, 정렬된 후에도 중복된 숫자의 순서가 입력에서의 순서와 동일한 상태
✔️ 알고리즘
RadixSort
입력: n개의 r진수의 k자리 숫자
출력: 정렬된 숫자
for i=1 to k
각 숫자의 i자리 숫자에 대해 안정한 정렬을 수행한다.
return 배열 A✔️ 시간 복잡도
for-루프가 k번 반복
O(n+r) 시간 소요
시간 복잡도는 O(k(n+r)) --> k,r이 n보다 작으면, O(n)
✔️ LSD(Least Significant Digit) 기수 정렬
- 1의 자리부터 k자리로 정렬 진행
- RL(Right-to-Left), 오른쪽에서 왼쪽으로 진행하는 기수 정렬
✔️ MSD(Most Significant Digit) 기수 정렬
- k자리부터 1의 자리로 정렬 진행
- LR(Left-to-RIght), 왼쪽에서 오른쪽으로 진행하는 기수 정렬
- LSD 보다 복잡
