요소 'x'가 Ω (log (n)) 실행 시간에 정렬 된 배열에 있는지 확인하는 방법은 무엇입니까?

Question

x 요소가 정렬 된 배열에 속하는지 AΩ(log(n)) 런타임에 결정할 수 있습니까?

나의 초기 대답 : 우리가 이진 검색을 사용하고, 그 높이 (n)은 적어도 log_3 것을 보여줄 수있는 의사 결정 트리, 높이 h에 따라서 삼항 트리를 만들 수는 ∈ Ω 3^h 잎 따라서 log_3 (n)을 가지고 (log (n))이다.

Answer 1

결정 트리는 좋은 본능입니다. 이제 나무를 실제로 만들지는 않겠지 만, 어쨌든 그것을 통해 동일한 검색을 수행하십시오 ....