リニアサーチアルゴリズムの平均実行時間

Question

確定リニアサーチアルゴリズムの平均実行時間を導出しようとしています。このアルゴリズムは、配列A [1]、A [2]、A [3] ... A [n]の順序でソートされていない配列Aの要素xを検索します。それは要素xを見つけるか、配列の終わりに達するまで続きます。私はwikipediaを検索し、与えられた答えは（x + 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の順列については忘れてしまいました。

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 

---

を以下の私のコメントについて詳しく説明するには：すべての要素が異なっていることを前提とし、xをP(i)の正しい定義は、私がMathematicaに物事を裏返します

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

ですマッチの集合をYとし、不一致の集合をYとする。仮定によって、| X | = kおよび| Y | = n-kである。予想読み取り回数は、eが読み取られる確率eの要素eに対する合計に等しくなります。

Sの各要素が与えられれば、Sの各要素は確率1/| S |を持つ他のすべての要素の前に来ます。

Xの要素xは、確率1/kであるXの他のすべての要素の前に来る場合にのみ読み込まれます。 Xにおける要素の総寄与は| X |である。 （1/k）= 1

Yの要素yは、確率1 /（k + 1）であるXのすべての要素の前に来る場合にのみ読み込まれます。 Yの要素の合計寄与は| Y |である。 （1 /（k + 1））=（n-k）/（k + 1）となる。

1 +（n-k）/（k + 1）=（n + 1）/（k + 1）である。

Answer 2

ここには、コルマンの用語を使用するソリューションがあります。 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)。