IT용어위키

비교 트리 모델(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와 비교하여 적절한 순서를 결정한다.

이 과정을 트리로 나타내면 다음과 같다.

        A ? B
       /    \
    C ? A   C ? B
   /    \   /    \
 ABC   ACB BAC   BCA

이 비교 트리는 모든 가능한 정렬 순서를 고려하여 최적의 비교 연산 수를 결정한다.

비교 기반 정렬의 하한 증명

비교 트리 모델을 사용하면 비교 기반 정렬 알고리즘이 최소한 Ω(n log n)의 비교 연산을 수행해야 함을 증명할 수 있다.

n개의 원소를 정렬하는 경우 가능한 순열의 수는 n!이다.
결정 트리의 리프 노드는 가능한 정렬된 배열의 모든 경우를 포함해야 한다.
깊이가 d인 결정 트리는 최대 2^d개의 리프 노드를 가질 수 있다.
따라서, 다음 부등식을 만족해야 한다.
- n! ≤ 2^d
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) 비용과 메모리 사용량이 고려되어야 한다.