비교 트리 편집하기

비교 트리 모델(Comparison Tree)는 비교 연산을 사용하여 문제를 해결하는 알고리즘을 분석하는 데 사용되는 개념적인 모델이다. 이 모델은 주어진 입력 요소들 간의 비교 연산을 기반으로 결정 트리(Decision Tree)를 구성하며, 정렬 및 선택 문제의 하한을 분석하는 데 활용된다.
==개요==
비교 트리 모델에서는 입력 데이터가 트리의 루트에서 시작하여 내부 노드에서 비교 연산을 수행하고, 비교 결과에 따라 다른 하위 노드로 이동하는 방식으로 동작한다. 트리의 리프 노드(Leaf Node)는 최종적인 정렬 결과나 선택 결과를 나타낸다.

이 모델을 통해 특정 문제의 최적 비교 횟수 하한을 증명할 수 있으며, 특히 비교 기반 정렬 알고리즘의 최소 시간 복잡도를 분석하는 데 중요한 역할을 한다.
==비교 트리 모델의 구성 요소==
*'''노드(Node)''': 각 노드는 비교 연산을 나타낸다.
*'''에지(Edge)''': 비교 결과(True/False)에 따라 다른 하위 노드로 이동한다.
*'''루트(Root)''': 비교 트리의 시작점.
*'''리프 노드(Leaf Node)''': 최종 결과(예: 정렬된 순서, 선택된 원소)를 나타낸다.
==비교 트리 모델의 예제==
예를 들어, 세 개의 원소 {A, B, C}를 정렬하는 문제를 비교 트리 모델로 표현하면 다음과 같다.

1. A와 B를 비교한다.

* A ≤ B이면 왼쪽 서브트리로 이동
* A > B이면 오른쪽 서브트리로 이동

2. 이후 C와 비교하여 적절한 순서를 결정한다.

이 과정을 트리로 나타내면 다음과 같다.<syntaxhighlight lang="plaintext">
        A ? B
       /    \
    C ? A   C ? B
   /    \   /    \
 ABC   ACB BAC   BCA
</syntaxhighlight>이 비교 트리는 모든 가능한 정렬 순서를 고려하여 최적의 비교 연산 수를 결정한다.
==비교 기반 정렬의 하한 증명==
비교 트리 모델을 사용하면 비교 기반 정렬 알고리즘이 최소한 Ω(n log n)의 비교 연산을 수행해야 함을 증명할 수 있다.
*n개의 원소를 정렬하는 경우 가능한 순열의 수는 '''n!'''이다.
*결정 트리의 리프 노드는 가능한 정렬된 배열의 모든 경우를 포함해야 한다.
*깊이가 d인 결정 트리는 최대 '''2<sup>d</sup>'''개의 리프 노드를 가질 수 있다.
*따라서, 다음 부등식을 만족해야 한다.
**n! ≤ 2<sup>d</sup>
*Stirling 근사를 사용하면,
**d = Ω(n log n)
*따라서, 어떤 비교 기반 정렬도 평균적으로 Ω(n log n)보다 빠를 수 없다.
==선택 문제(Selection Problem)에서의 비교 트리==
선택 문제(예: k번째 최소 원소 찾기)에서도 비교 트리 모델을 적용할 수 있다.
*최솟값 찾기: n-1번 비교 (O(n))
*최댓값 찾기: n-1번 비교 (O(n))
*최솟값과 최댓값 동시에 찾기: 3n/2 - 2번 비교 (O(n))
*k번째 최소 원소 찾기: O(n) (Median of Medians 알고리즘 사용 시)
==비교 트리 모델의 한계==
*비교 기반 모델에서만 성립하며, '''카운팅 정렬''', '''기수 정렬''', '''버킷 정렬'''과 같은 비교 기반이 아닌 정렬 알고리즘에는 적용되지 않는다.
*실제 구현에서는 분기(branching) 비용과 메모리 사용량이 고려되어야 한다.
==같이 보기==
*[[정렬 알고리즘]]
*[[비교 기반 문제]]
*[[결정 트리]]
*[[시간 복잡도 분석]]