[알고리즘] 정렬의 하한 증명

정렬의 하한은 결정트리로 증명할 수 있다.

3개의 자료를 정렬 할 때 나올 수 있는 경우는 3!으로 총 6가지이다.

이 말은 총 6가지 중 하나는 참인 경우가 존재한다는 것이다.

 

6가지 중 하나의 도착하는 시간은 결정 트리의 높이에 따른다

 

결정트리는 이진 트리로 이루어져 있으므로 총 n!의 리프트리를 가지고 있다

이 결정트리의 높이는 height = log n!

n!는 stirling's formula(스털링 근사)정의에 의해 nlogn으로 정의될 수 있다

 

그러므로 

H=nlogn이 될 수있고

 

비교정렬에서 최소의 시간 복잡도는 O(nlogn)이 된다.

https://ict-nroo.tistory.com/57