선형 검색 알고리즘의 평균 사례 실행 시간

Question

결정 성 선형 검색 알고리즘의 평균 사례 실행 시간을 도출하려고합니다. 알고리즘은 정렬되지 않은 배열 A의 요소 x를 A [1], A [2], A [3] ... A [n]의 순서로 검색합니다. 요소 x를 찾거나 배열의 끝에 도달 할 때까지 계속됩니다. 나는 wikipedia을 검색했고 주어진 답은 (n + 1)/(k + 1)이었습니다. 여기서 k는 x가 배열에있는 횟수입니다. 나는 다른 방법으로 접근했고 다른 대답을 얻고있다. 아무도 내게 올바른 증거를주고 내게도 내 방법에 문제가 있다는 것을 알려주시겠습니까?

E(T)= 1*P(1) + 2*P(2) + 3*P(3) ....+ n*P(n) where P(i) is the probability that 
        the algorithm runs for 'i' time (i.e. compares 'i' elements). 
P(i)= (n-i)C(k-1) * (n-k)!/n! 
Here, (n-i)C(k-1) is (n-i) Choose (k-1). As the algorithm has reached the ith 
step, the rest of k-1 x's must be in the last n-i elements. Hence (n-i)C(k-i). 
(n-k)! is the total number of ways of arranging the rest non x numbers, and n! 
is the total number of ways of arranging the n elements in the array. 

단순화시 (n + 1)/(k + 1)을 얻지 못합니다.

Answer 1

k 개의 x 사본 순열에 대해서는 잊어 버린 것입니다. , 모든 요소가 별개 가정 X가를하자 :

In[1]:= FullSimplify[Sum[i Binomial[n-i, k-1]/Binomial[n, k], {i, 1, n}], 0 <= k <= n] 

     1 + n 
Out[1]= ----- 
     1 + k 

---

아래 내 댓글에 정교하게하려면 P(i)의 정확한 정의는

P(i) = (n-i)C(k-1) * k! * (n-k)!/n! = (n-i)C(k-1)/nCk. 
        ^^ 

내가 티카에 걸쳐 물건을 돌려 것입니다 일치 집합을 선택하고 Y를 일치하지 않는 집합이라고 가정합니다. 가정에 따라, | X | = k 및 | Y | = n-k이다. 예상 읽기 수는 e가 읽히는 확률 인 요소 e에 대한 합계와 같습니다.

S의 각 요소가 주어지면 S의 각 요소는 확률이 1/| S | 인 다른 모든 요소보다 먼저옵니다.

X의 원소 x는 확률 1/k 인 X의 모든 원소 앞에 오는 경우에만 읽습니다. X에서 요소의 총 기여도는 | X | (1/k) = 1

확률 1/(k + 1) 인 X의 모든 원소 앞에 오는 경우에만 Y의 원소 y가 읽혀집니다. Y에있는 요소들의 총 기여도는 | Y |이다. (1/(k + 1)) = (n-k)/(k + 1)이다.

우리는 1 + (n-k)/(k + 1) = (n + 1)/(k + 1)을 갖는다.

Answer 2

다음은 Cormen 용어를 사용하는 솔루션입니다. S을 다른 n-k 요소 집합이라고합시다.
우리가 실행하는 과정에서 집합의 i '번째 요소 이 발생하면 지표가 임의의 변수 Xi=1으로 변경됩니다.
Pr{Xi=1}=1/(k+1)이고 따라서 E[Xi]=1/(k+1)입니다.
우리가 실행 과정에서 검색하는 요소 중 하나 인 k을 발견하면 지시기를 임의의 변수 Y=1으로 변경하십시오.
Pr{Y=1}=1 따라서 E[Y]=1.
랜덤 변수 X=Y+X1+X2+...X(n-k)을 이 실행되는 과정에서 만나는 요소의 합계라고합시다.
E[X]=E[Y+X1+X2+...X(n-k)]=E[Y]+E[X1]+E[X2]+...E[X(n-k)]=1+(n-k)/(k+1)=(n+1)/(k+1).