線性搜索算法的平均個案運行時間

我正在嘗試推導確定性線性搜索算法的平均個案運行時間。該算法以A [1]，A [2]，A [3] ... A [n]的順序搜索未排序數組A中的元素x。它在找到元素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）。

來源

2011-02-26 Brahadeesh

也許我是個笨蛋，但是如果數組大小爲N，那麼不是平均情況時間N/2？ Nevermind ...不應該從我的iPhone發表評論...誤讀了q – Kevin

@kevin它沒有重複的情況。但是當你有重複時，即使你發現第二次出現（爲了計算平均複雜度），你將首先在你的搜索中獲得。 – Zimbabao

@Kevin實際上沒有多重拷貝情況的平均情況是（n + 1）/ 2。它可以這樣得到：1 *（1/n）+ 2 *（1/n）+ 3 *（1/n）... + n *（1/n）。 – Brahadeesh

您已經忘記了k副本x的排列組合。的P(i)正確的定義是

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

我要把事情交給數學：

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 | = n-k。期望的讀取次數等於讀取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））=（n-k）/（k + 1）。我們有1 +（n-k）/（k + 1）=（n + 1）/（k + 1）。

來源

2011-02-26 13:30:06 user635541

注意：推導這個值的一個更簡單的方法是觀察只有1個x被檢查，並且檢查每個nk非x是否出現在所有x之前，這是概率1 /（k + 1 ）。我們有1 +（n-k）/（k + 1）=（n + 1）/（k + 1）。 – user635541

@ user635541感謝您的結果。我確實想過排列x的。但是，它們會產生相同陣列的多個副本。因此，我決定反對他們。你能否澄清使用k的理由！？另外，你能否詳細說明評論？我不明白。抱歉。 – Brahadeesh

問題是，n！因素也會導致k！相同數組的副本（假設非x是不同的）。 – user635541

下面是使用Cormen術語的解決方案：讓S爲其他n-k元素的集合。
如果我們在執行過程中遇到集合S的i第012個元素，那麼讓指標隨機變量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)。

來源

2012-01-21 11:47:12

我個人發現Y的解釋有點混亂。如果對別人有幫助，另一種想法是讓X =（不匹配的元素的數量）和Y =（匹配的元素的數量）。然後，我們正在尋找Z =（訪問元素的數量）= X + Y，但Y = 1，概率爲1，所以E [X] = E [X] + E [Y] = E [X] + 1 –

線性搜索算法的平均個案運行時間

回答

相關問題