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

Question

我试图推导出确定性线性搜索算法的平均案例运行时间.该算法按照A [1],A [2],A [3] ...... A [n]的顺序搜索未排序数组A中的元素x.它在找到元素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)简化.

Answer 1

你忘了考虑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.

当且仅当它出现在X的每个元素之前时,才读取Y中的元素y,即概率1 /(k + 1).Y中元素的总贡献是| Y | (1 /(k + 1))=(nk)/(k + 1).

我们有1 +(nk)/(k + 1)=(n + 1)/(k + 1).

Answer 2

这是一个使用Cormen术语的解决方案:让我们S成为其他n-k元素的集合.如果我们在执行过程中遇到集合的第th个元素,那么
让指标随机变量.因此.如果我们在执行过程中遇到我们正在搜索的任何元素,那么 让指标随机变量.因此. 让随机变量是我们在执行过程中遇到的元素的总和..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)