다음 중 데이터 값의 대소를 비교하여 정렬하는 문제에 대한 가장 빠른 … | [계리직 컴퓨터일반] 12년 1회차 기출문제 상세 페이지

값의 대소 비교로 정렬하는 비교 기반 정렬이 최악의 경우에 달성할 수 있는 가장 빠른 시간 복잡도는 $O(n\log_2 n)$이다.
n개 원소의 가능한 순서는 $n!$가지이고, 비교 한 번은 결과를 둘로 나누므로 최소 $\log_2 n!$번의 비교가 필요하며 이는 $n\log_2 n$에 비례한다. 합병 정렬·힙 정렬이 이 하한을 달성한다.
$O(n)$: 계수 정렬·기수 정렬처럼 비교를 쓰지 않는 정렬에서나 가능하며, 비교 기반 정렬은 최악의 경우 이에 도달할 수 없다.
$O(\log_2 n)$: 정렬된 배열의 이진 탐색 복잡도로, 모든 원소를 한 번씩 보는 것조차 불가능한 시간이다.
$O(n^2)$: 버블·선택·삽입 정렬의 복잡도로, 가장 빠른 알고리즘이 아니다.