정보 이론적 하한 편집하기 (부분)

==탐색 문제의 정보 이론적 하한==
정렬되지 않은 리스트에서 원소를 탐색하는 경우, 최악의 경우 O(n)의 시간이 필요하다. 그러나 이진 탐색(Binary Search)을 이용하면 O(log n)의 시간에 탐색할 수 있다.

이진 탐색이 O(log n)보다 빠를 수 없는 이유는 다음과 같다.
*n개의 원소에서 하나를 찾는 경우 가능한 상태 수는 n이다.
*각 비교는 두 개의 선택지만 제공하므로, 결정 트리의 깊이 d는 다음을 만족해야 한다.
**n ≤ 2<sup>d</sup>
*따라서, d = Ω(log n)
이는 정렬된 배열에서 탐색을 수행할 때 O(log n)이 정보 이론적으로 최적임을 의미한다.