결정 트리
어떤 선택을 하기 위한 알고리즘을 트리로 나타내면 결정 트리라 한다. 각 중간 정점은 질문이고 각 질문에 대한 답이 적힌 간선을 타고 내려가는 형태로 구성되어 있다. 의사 결정 트리라고도 한다.
결정 트리의 높이는 해당 문제를 해결하기 위한 최악의 상황에서의 선택 횟수이다. 즉 결정 트리는 어떤 문제를 해결하기 위해 필요한 최악의 시간의 경우에 대한 하한을 제시하는데 사용 가능하다.
5개의 동전 문제
5개의 동전 중 하나의 동전만 무게가 다르다면 어떤 동전이 무게가 다르고, 다른 동전보다 무거운지 가벼운지를 알 수 있는 결정 트리이다.
최악의 경우 시간을 최악의 경우에 필요한 무게 비교의 수로 정의한다면 최악의 경우 시간은 결정 트리의 높이인 $ 3 $이다. 만약 최악의 경우에도 $ 2 $ 이하의 시간에 해결하는 알고리즘이 있다고 가정하면 높이가 $ 2 $인 결정 트리로 기술될 수 있어야 한다. 이러한 트리는 말단 정점이 많아야 $ 9 $개 이다. 그런데 $ 5 $개의 동전이 무겁고 가볍고의 경우의 수는 $ 10 $개이므로 모순된다. 따라서 최악의 경우 시간은 $ 3 $이다.
세 수를 정렬하는 알고리즘의 결정 트리
아래 결정 트리에 제시된 알고리즘의 최악의 경우 비교의 수는 $ 3 $이다. 3 개를 나열할 수 있는 경우의 수는 $ 3! = 6 $ 이므로 높이가 $ 2$인 결정 트리로는 기술 불가능하다.
$ n $ 개를 정렬하는 데에 필요한 최악의 경우 비교의 수는 $ \mathcal{\Omega} (n \lg n) $ 이다.
