알고리즘
정렬의 Lower Bound
llilliiillliill
2017. 12. 12. 14:25
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.
정렬의 Lower Bound
정렬 알고리즘의 유형
Comparison Sort
- 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 알고리즘
- 따라서 데이터들 간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등)
- 버블 소트, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등
Non-Comparison Sort
- 정렬할 데이터에 대한 사전 지식을 이용 - 적용에 제한
- Bucket Sort
- Radix Sort
정렬 문제의 하한
어떠한 경우에도 모든 Comparison Sort의 시간복잡도는 Θ(nlogn) 보다 낮을 수 없다를 증명
하한(Lower Bound)
- 입력된 데이터를 한번씩 다 보기위해서 최소 Θ(n)의 시간복잡도 필요
- 합병 정렬과 힙 정렬 알고리즘들의 시간복잡도는 Θ()
- 어떤 Comparison Sort 알고리즘들도 Θ()보다 나을 수 없다.