삽입, 버블, 퀵, 합병, 힙 정렬의 시공간복잡도와 정렬 알고리즘의 하한계

1. 키 비교 정렬 알고리즘들

• 위 정렬들은 대표적인 키 비교 정렬 알고리즘이다. 이 중에서 일반적으로 퀵 정렬이 가장 빠르다고 알려져있다. 최악의 경우에는 O(n log n)으로 합병정렬과 힙정렬이 가장 빠르다. 그렇다면 최악의 경우에 이들보다 더 좋은 알고리즘은 없을까?

2. 키 비교 정렬 알고리즘의 하한계

• 키 비교에 의한 정렬 알고리즘은 판단트리로 나타낼 수 있다.

• 예를 들어 (x1, x2, x3) 배열에 대한 삽입 정렬의 판단 트리는 아래와 같다.

• 키 비교 정렬 알고리즘은 n!개 결과를 낼 수 있다(리프노드가 n!개 이다).
• 그리고 이진트리는 높이가 h일때 최대 2^h의 리프 노드를 가질 수 있다.
• 즉 2^h >= n!를 만족해야한다. 양변에 로그를 취하면 h >= log n! 이다. 최악의 경우 정렬 알고리즘은 h번 비교하므로 최소 log n!번 비교 연산을 한다.

• 위의 계산에 따라서 키 비교에 의한 정렬 알고리즘의 최악의 경우 시간복잡도는 Ω(n log n)이므로 O(n log n)보다 효율적인 최악의 경우 키 비교 알고리즘은 있을 수 없다.