바이너리 검색의 최적 성

Question

이것은 바보 같은 질문 일 수 있지만 이진 검색이 점근 적으로 최적이라는 증거를 알고있는 사람이 있습니까? 즉, 객체에 대해 유일하게 허용 된 연산이 비교 인 요소의 정렬 된 목록이 주어지면 검색이 o (lg n)에서 수행 될 수 없다는 것을 어떻게 증명할 수 있습니까? (이것은 lg n의 작은 것입니다.)이 작업을 허용하는 유일한 연산이 비교 인 요소로 제한하고 있음을 주목하십시오. O (lg n)을 기대할 수있는 잘 알려진 알고리즘이 있기 때문입니다 데이터에 대해 더 복잡한 연산을 수행 할 수 있다면 (예를 들어, 보간법 검색 참조).

Answer 1

:

가

• 가능한 결과의 개수가 적어도 O (N)이어야한다.
• "결정 트리"의 노드에 의해 알고리즘에 의해 수행 된 결정을 나타낼 수 있습니다. 항목이 더 큰 경우 비교가 진행되고, 그렇지 않은 경우에는 다른 방식으로 진행됩니다. 트리의 노드는 알고리즘의 상태이고 잎은 결과입니다. 따라서 트리에 적어도 O (n) 개의 노드가 있어야합니다.
• O (n) 노드의 각 트리는 적어도 O (log N) 레벨을가집니다.

Answer 2

논리가 간단합니다. n 개의 정렬 된 요소가 있다고 가정 해 보겠습니다.

1. 1 개의 비교 결과 (첫 번째 요소가 작거나 더 높음)가 있습니다. 따라서 한 번의 비교로 충분하면 n <= 2입니다. 그렇지 않은 경우 3 개의 요소 (a, b, c)가 있고 알고리즘에 2 개의 가능한 결과가있는 경우 3 개의 요소 중 하나가 선택되지 않습니다.
2. 2 가지 비교 결과가 네 가지가 될 수 있습니다. 따라서 2 번의 비교로 충분하다면 n <= 4.
3. 이와 마찬가지로, k의 비교가 충분할 경우 n은 n <= 2^k이어야합니다.

마지막 부등식을 반대로하면 로그가됩니다 : k >= log(2, n). here 가입일

Answer 3

Nikita가 설명했듯이 은 항상을 O (log n)보다 더 좋게 만들 수 없습니다.

몇 가지 추가 작업을 수행 할 수 있더라도 여전히 충분하지 않습니다. 보간 검색이 바이너리 검색보다 성능이 떨어지는 요소 시퀀스를 준비 할 수 있다고 확신합니다.

우리는 때문에 보간 검색이 낫다 말할 수있다 : 우리는 평균 성능이 아니라 최악의 경우를 고려

1. .
2. 각 가능한 들어오는 데이터 집합의 확률이 균일하지 않습니다.

답변은 - 들어오는 데이터 세트에 대한 추가 지식에 달려 있습니다.