mid - high - 2를 계산하는 수정 된 이진 탐색에 대한 시간 복잡도

Question

분할 점을 mid = high - 2 (mid = (low + high)/대신)로 계산하는 이진 검색의 시간 복잡성을 알아야합니다. 2) 수정 알고리즘이 얼마나 느리거나 빠를 지 알 수 있습니다.

Answer 1

최악의 시나리오는 검색된 항목이 맨 처음 인 것입니다. 이 경우 항상 n에서 2를 빼기 때문에 대략 n/2 단계를 가지게되어 선형 복잡성을 갖게됩니다. 가장 좋은 경우는 검색된 항목이 정확하게 n-2에 있고, 이는 일정한 복잡성을 취할 것입니다. n -> 무한대가 선형 적이라고 가정하면 평균 복잡도.

Answer 2

힌트 : 이진 검색의 반복 수식을 기반으로 해답을 얻을 수 있습니다.

우리는 T (N) = T가 (플로어 (N/2)) + 우리가 동일한 두 halfs입니다로 나누기 때문에 O (1)

우리 바닥이 (N/2). 수정 된 버전을 설명하기 위해 해당 수식을 다시 작성해야합니다. 또한, Akra-Bazzi 방법을 사용하여 수정 된 버전의 재귀 수식을 해결해야합니다. 두 개의 불균형 한 반으로 나누기 때문입니다.