[Discrete Mathematics] 결정 트리(decision tree) 및 최소 시간

---

결정 트리

 

어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.

점심 메뉴를 결정하는 결정 트리 (배고프다)

결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다.

 

---

5개의 동전 문제

 

5개의 동전 중 하나의 동전만 무게가 다르다면 어떤 동전이 무게가 다르고, 다른 동전보다 무거운지 가벼운지를 알 수 있는 결정 트리이다.

최악의 경우 시간을 최악의 경우에 필요한 무게 비교의 수로 정의한다면 최악의 경우 시간은 결정 트리의 높이인 $ 3 $이다. 만약 최악의 경우에도 $ 2 $ 이하의 시간에 해결하는 알고리즘이 있다고 가정하면 높이가 $ 2 $인 결정 트리로 기술될 수 있어야 한다. 이러한 트리는 말단 정점이 많아야 $ 9 $개 이다. 그런데 $ 5 $개의 동전이 무겁고 가볍고의 경우의 수는 $ 10 $개이므로 모순된다. 따라서 최악의 경우 시간은 $ 3 $이다.

 

---

세 수를 정렬하는 알고리즘의 결정 트리

 

아래 결정 트리에 제시된 알고리즘의 최악의 경우 비교의 수는 $ 3 $이다. 3 개를 나열할 수 있는 경우의 수는 $ 3! = 6 $ 이므로 높이가 $ 2$인 결정 트리로는 기술 불가능하다.

$ n $ 개를 정렬하는 데에 필요한 최악의 경우 비교의 수는 $ \mathcal{\Omega} (n \lg n) $ 이다.