정렬의 하한 - 3개 요소에 대한 삽입 정렬을 위한 결정 트리

 

우선 상황을 가정해봅시다.

3개 요소 1, 2 ,3으로 나열 될 수 있는 경우의 수는 다음과 같습니다.

<1,2,3>, <1,3,2>, <2,1,3>, <2,3,1>, <3,1,2>, <3,2,1>

 

3개 요소들을 각각 a1, a2, a3라고 인덱스를 지정하도록하겠습니다.

 

다시한번 상기시키자면 지금 우린 삽입정렬을 하고 있습니다. 그런데 이제 요소 3개씩 조합들을 곁들인.

그래서 첫번째 조합을 보자면 <1,2,3>으로 되어있습니다.

삽입정렬 기억 나시죠? 첫 번째 인덱스 요소부터 정렬을 시작합니다.

그러면 a1인 1과 a2인 2가 서로 비교 대상이 됩니다.

이걸 먼저 루트 노드로 그려보자면

(a1, a2)가 되겠습니다. 이때 key 값은 a2가 됩니다.

그 다음은 a2와 a3 값이 서로 비교대상이 됩니다.

이 때는 key 값이 a3가 됩니다.

 

a1(1)이 a2(2)보다 작거나 같으면 a2(2)랑 a3(3)이랑 비교하면 되기 때문에

왼쪽 하위노드로 두었습니다.

이제 a2(2)가 a3(3)보다 작거나 같은지 체크해보면됩니다. 

이경우 더이상 비교할 필요가 없으니 유일한 <1,2,3> 경우가 될겁니다.

 

<1,2,3>, <1,3,2>, <2,1,3>, <2,3,1>, <3,1,2>, <3,2,1>

 

이번에는 맨 뒤의 숫자 <3,2,1> 조합을 생각해봅시다.

이 경우 a1(3)이 a2(2)보다 크기 때문에 오른쪽 하위 노드에 들어갑니다.

이 때 key 값은 a2가 입니다.

 

그리고 이제 a1(3)이 a3(1)보다도 크기 때문에 성립하네요

 

 

이제 a1이 a2와 a3보다 크다는걸 알았으니 a2가 a3보다 작은지만 비교하면 되겠네요.

역시나 이번에도 <3,2,1>은 성립하는걸 보았으니 오른쪽 루트의 리프노드는 <3,2,1>이 되겠네요.

 

이 때 a1와 a2비교한 후 스왑을 해줍니다. 이 때 배열은 <2,3,1> 이고 key값은 a3입니다.

 

이런식으로 나머지 배열들도 다 정리를 해보면 아래 사진과 같습니다.

 

 

그리고 여기에 최선의 케이스 오메가와 최악의 케이스 빅 오를 그려보면

이렇게 되겠습니다.

우리가 지금까지 한건 세 개의 요소로 삽정렬의 결정 트리를 구성한겁니다.

결정 트리에는 두 가지 중요한 점이 있습니다

1. 결정 트리의 잎(leaves) 개수:
   - 결정 트리에는 최소한 n! (n 팩토리얼) 개의 잎이 있습니다.
   - 이유: 모든 가능한 순열(permutation)이 최소 한 번씩 나타나야 하기 때문입니다.
   - 예: 3개 요소의 경우, 3! = 6개의 순열이 있으므로 최소 6개의 잎이 있어야 합니다.

2. 루트에서 잎까지의 가장 긴 경로 길이:
   - 이는 사용하는 정렬 알고리즘에 따라 다릅니다.
   - 예시:
     a) 삽입 정렬(Insertion sort): Θ(n²)
        - 최악의 경우, n²에 비례하는 비교 횟수가 필요합니다.
     b) 병합 정렬(Merge sort): Θ(n lg n)
        - 항상 n log n에 비례하는 비교 횟수가 필요합니다.

이걸 통해 각 정렬 알고리즘의 시간 복잡도를 이해하는 데 도움이 됩니다. 

결정 트리의 구조가 알고리즘의 성능을 직접적으로 반영한다는 것을 보여줍니다.

 

---

 

결정 트리 증명

정렬 알고리즘의 결정 트리에 대한 중요한 정리와 그 증명을 보겠습니다.

1. 정리: n개 요소를 정렬하는 모든 결정 트리의 높이는 Ω(n lg n)입니다.

2. 증명 과정:
   - 트리의 높이 h는 최소한 lg(n!)보다 크거나 같아야 합니다.

 - 스털링 근사(Stirling's approximation)를 사용하여 n!을 근사합니다

 

   - 로그를 취하고 계산을 진행하면 h ≥ n lg(n/e)가 됩니다.
   - 이를 전개하면 h ≥ n lg n - n lg e가 됩니다.

   - 결과적으로 h = Ω(n lg n)임을 보입니다.

 

h ≥ n lg n - n lg e 에서 Ω(n lg n)이 되는 과정은 다음과 같습니다:

1. n lg e는 상수항입니다:
   - lg e는 고정된 값(약 1.44)이므로, n lg e는 n에 비례하는 선형 항입니다.

2. 점근적 표기법에서는 상수항과 낮은 차수의 항을 무시합니다:
   - n lg n은 n lg e보다 더 빠르게 증가합니다.
   - 따라서 n이 충분히 큰 경우, n lg n이 n lg e를 지배합니다.

3. 결과적으로:
   h ≥ n lg n - n lg e
   ≥ n lg n - O(n)
   = Ω(n lg n)

즉, h의 하한(lower bound)은 n lg n에서 선형 항을 뺀 것이지만, 점근적으로는 이 선형 항이 무시되어 결국 Ω(n lg n)이 됩니다.

이는 "h는 최소한 n lg n의 order로 증가한다"는 의미로, 모든 비교 기반 정렬 알고리즘의 시간 복잡도 하한을 나타냅니다.

 

결론은 어떤 비교 기반 정렬 알고리즘도 Ω(n lg n)보다 빠를 수 없다는 것을 수학적으로 보여줍니다.