정렬의 Lower Bound

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.

정렬의 Lower Bound

정렬 알고리즘의 유형

Comparison Sort

- 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 알고리즘

- 따라서 데이터들 간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등)

- 버블 소트, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등

Non-Comparison Sort

- 정렬할 데이터에 대한 사전 지식을 이용 - 적용에 제한

- Bucket Sort

- Radix Sort

정렬 문제의 하한

어떠한 경우에도 모든 Comparison Sort의 시간복잡도는 Θ(nlogn) 보다 낮을 수 없다를 증명

하한(Lower Bound)

- 입력된 데이터를 한번씩 다 보기위해서 최소 Θ(n)의 시간복잡도 필요

- 합병 정렬과 힙 정렬 알고리즘들의 시간복잡도는 Θ()

- 어떤 Comparison Sort 알고리즘들도 Θ()보다 나을 수 없다.