정렬의 하한점에 대해

정렬의 하한점 (Lower bound)

정렬 알고리즘의 유형

- Comparison Sort

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

따라서 데이터들 간의 크기 관계가 정의되어 있다면 어떤 데이터든 적용이 가능해진다. (문자열, 알파벳, 기타 따로 정의된 객체 등)

버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등이 있다.

- Non - Comparison Sort

정렬할 데이터에 대한 사전지식을 이용한다. 하지만 이는 적용범위가 제한적이라는 한계가 있다.

Bucket Sort와 Radix Sort가 대표적으로 알려져있는 정렬 방식이다.

정렬 문제의 최저점

- 최저점 (Lower bound)

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

합병 정렬과 힙 정렬 알고리즘의 시간복잡도는 O($nlog_2{n}$)이다.

어떠한 Comparison Sort알고리즘도 O($nlog_2{n}$)보다 더 빨라질 수는 없다.

Decision Tree

- Abstraction of any comparison sort

-3개의 값을 정렬하는 삽입 정렬에 대한 decision tree.

입력 데이터 중 1, 2 ,3번째라는 뜻이다.

1과 2를 비교해 2가 더 크면 2와 3을 비교한다.

3이 2보다 작다면 1과 비교해 3이 더 작으면 최종적으로 3, 1, 2의 순으로 정렬한다는 예시이다.

위 결정 트리에서의 리프 갯수는 n!개라고 할 수 있다. (n은 비교할 데이터의 수이다.)

- 리프 노드의 개수는 n!개이다. 이유로는 모든 순열 (Permutation)에 해당하기 때문이다.

- 최악의 경우 시간 복잡도는 트리의 높이와 같은 시간이 소요된다.

- 트리의 높이를 최대한 줄이면서 리프 노드의 개수를 최대화하려고 한다면 결국 완전 이진 트리의 형태를 띄게 된다.

- 트리의 높이

height ≥ $log_2{n}$ = O(n$log_2{n}$) => Stirling Theory