무작위 바이너리 검색의 실행 시간

Question

이진 검색의 다음 무작위로 랜덤 화 된 변형을 고려하십시오. 정렬 된 배열 n 개의 정수 중 A와 찾고자하는 정수 v가 A에서 무작위로 균등하게 선택됩니다.그런 다음 v를 배열 중간의 값과 비교하는 대신 임의 화 된 이진 검색 variant는 1에서 n까지 임의의 숫자 r을 선택하고 v와 A [r]을 비교합니다. v가 더 크거나 작 으면이 프로세스는 v의 위치가 발견 될 때까지 왼쪽 하위 배열 또는 오른쪽 하위 배열 에서 반복적으로 반복됩니다. 이 알고리즘의 예상 실행 시간에 대한 경계를 입증하십시오. 여기

내가 T (N)에 대해 가지고 무엇을

T(n) = T(n-r) + T(r) + Θ(1)

는 그러나, 나는 얼마나 단단한 결합을 얻는 단서가 없다.

Answer 1

귀하의 T (n) 공식은 완전하지 않습니다. 사실,

모든 사례를 살펴 봅니다. 임의의 지점을 가로 지르는 배열을 분할하여 문제의 크기를 줄이면 감소 된 하위 문제의 확률은 1에서 n 사이가됩니다. 따라서 1/n 확률로 검색 공간은 r이됩니다. 그래서 예상 실행 시간 수를 T (n)을 제공

T(n) = sum (T(r)*Pr(search space becomes r)) + O(1) = sum (T(r))/n + O(1)

임의의 바이너리 종류의

T(n) = average(T(r)) + O(1)

하자 예상 시간 복잡도가된다.

T(n) = [ T(1)+T(2)+...+T(n)]/n + 1 
n*T(n) = T(1)+T(2)+...+T(n) + n 
(n-1)*T(n-1) = T(1)+T(2)+...+T(n-1) + n-1  [substituiting n by n-1] 
n*T(n) - (n-1)*T(n-1) = T(n) + 1 
(n-1)*T(n) - (n-1)*T(n-1) = 1 
(n-1)*T(n) = (n-1)*T(n-1) + 1 
T(n) = 1/(n-1) + T(n-1) 
T(n) = 1/(n-1) + 1/(n-2) + T(n-2)    [ T(n-1) = T(n-2) + 1/(n-2) ] 
... 
T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n) 
[ H(n) = reciprocal sum of first n natural numbers ] 

그래서

,

T(n) = O(log n)Harmonic number

bound of H(n)