임의의 인덱스로 배열을 검색 할 때 예상되는 루프 반복 양

Question

는 우리가 배열 A의 크기 N을 가지고 있다고 가정 해줍니다.첫 번째 인덱스와 n은 마지막 인덱스로 1입니다.여기에서는 x= k <= n

에서 x 발생 k 시간이있는 값 x가 포함됩니다.

우리는 검색 알고리즘을 그렇게하시는 경우 :

while true:
  i := random(1, n)
  if A[i] == x
    break

.

랜덤 (A, B)은 A에서 B까지 균일하게

이를 통해 X를 찾아서 프로그램을 종료 할 수있는 기회는 각 반복에 K / N입니다.그러나 내가 알고 싶은 것은 위에서 설명한 배열 A를 감안할 때이 프로그램에서 배열이 액세스 된 반복 수의 예상 값이 될 것입니다.

Answer 1

$ n $ 기하학적 r.v가되도록하십시오. 이는 성공적으로 찾을 때까지 $ a [x] $ 요소를 검색하기 위해 배열이 액세스 된 횟수를 반환합니다. 우리는 $ \ mathbb {e} [n] $ 을 알고 싶습니다.

우리는 $ p $ 의 확률 $ q= 1 - P $ 실패. 문제가 주어지면 $ a [x] $ 을 찾는 "성공"을 얻는 데 필요한 재판이 얼마나 많은 시도가 필요합니다. 따라서 while 루프가 종결됩니다. ...에

$ \ pr \ {n= k \}= q ^ {k-1} p $ , 우리는 $ \ mathbb {e} [n]=sum \ limits_ {k= 1} ^ \ infty k \ : q ^ {k-1} p $ .

이렇게 $ \ mathbb {e} [n]=dfrac 1p $ 여기서 $ p=dfrac kn $ so $ \ mathbb {e} [n]= dfrac nk $ .

평균적으로 요소를 찾기 전에 $ \ dfrac nk $ 액세스가 필요합니다. $ a [x] $ .