线性搜索算法的平均个案运行时间

我正在尝试推导确定性线性搜索算法的平均个案运行时间。该算法以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 –

线性搜索算法的平均个案运行时间

回答

相关问题