개발 공부 - [정렬] 정렬의 lower bound

 Comparison Sort

기존 것의 최선인 O(nlogn) 보다 더 좋은 시간복잡도 알고리즘을 위해!

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

- 따라서 데이터들간의 크기 관계가 정의되어 있으면, 어떤 데이터에든 적용가능

(문자열, 알파벳, 사용자 정의 객체 등)

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

Non-comparison sort

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

-  Bucket sort

- Radix sort

하한 (Lower bound)

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

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

- 어떤 comparison sort 알고리즘도 O(nlog2n)보다 나을 수 없다.

Decision Tree로 기재해서 보여 줌...

세가지 경우의 수 merge 하는 거 -.-)

Decision Tree

Leaf 노드의 개수는 n!개 (모든 순열에 해당)

최악의 경우 시간 복잡도는 트리 높이 

- 전체 트리의 높이가 n!일 때 전체 트리의 개수는 logn!을 넘을 수 없음

logn!= O(nlogn) = 스털링의 정의라는걸 이용하면 nlog2n 이라고 함

이진 트리의 경우 트리의 높이는

height ≥ log2n! = O(nlog2n)