5

決定論的線形探索アルゴリズムの平均ケース実行時間を導き出そうとしています。アルゴリズムは、ソートされていない配列Aの要素xをA [1]、A [2]、A [3] ...A[n]の順序で検索します。要素xが見つかると停止するか、配列の最後に到達するまで続行します。ウィキペディアで検索したところ、答えは（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）が得られません。

4

2 に答える 2

6

kのコピーの順列を説明するのを忘れましたx。の正しい定義P(i)は

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

私は物事をMathematicaに引き渡します：

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を一致のセットとし、Yを不一致のセットとします。仮定により、| X | =kおよび|Y| =nk。予想される読み取り数は、eが読み取られる確率の要素eの合計に等しくなります。

要素のセットSが与えられると、Sの各要素は、確率1 / |S|で他のすべての要素の前に来ます。

Xの要素xは、Xの他のすべての要素の前にある場合にのみ読み取られます。これは確率1/kです。Xの要素の合計寄与は|X|です。（1 / k）=1。

Yの要素yは、Xのすべての要素の前にある場合にのみ読み取られます。これは、確率1 /（k + 1）です。Yの要素の合計寄与は|Y|です。（1 /（k + 1））=（nk）/（k + 1）。

1 +（nk）/（k + 1）=（n + 1）/（k + 1）があります。

于 2011-02-26T13:30:06.993 に答える
6

これがコーメンの用語を使用する解決策です：他の要素Sのセットになりましょう。実行中にセットの'番目の要素に遭遇した場合は 、インジケーターを確率変数とします。したがって。実行中に検索している要素のいずれかに遭遇した場合は 、インジケーターを確率変数とします。したがって。 確率変数を、実行中に遭遇する要素の合計とします。。n-k
Xi=1iS
Pr{Xi=1}=1/(k+1)E[Xi]=1/(k+1)
Y=1k
Pr{Y=1}=1E[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)

于 2012-01-21T11:47:12.060 に答える