线性搜索算法的平均情况运行时间

Question

我正在尝试推导确定性线性搜索算法的平均情况运行时间。该算法按顺序在未排序的数组A中搜索元素x，顺序为A [1]，A [2]，A [3] ... A [n]。当它找到元素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)。

- Brahadeesh

---

也许我很蠢，但如果数组的大小为N，那么平均情况下的时间不就是N/2吗？算了...不应该从我的iPhone上发评论...我读错了问题。 - Kevin

@kevin 当不存在重复时，这是正常情况。但是当存在重复时，即使你正在寻找第二个出现的情况（计算平均复杂度），你也会在搜索中得到第一个。 - Zimbabao

@Kevin 实际上，对于没有多个副本的情况，平均情况是(n+1)/2。可以通过以下方式获得：1*(1/n)+2*(1/n)+3*(1/n)...+n*(1/n)。 - Brahadeesh

Answer 1

您忘记考虑 x 的 k 个副本的排列组合。正确的 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|=n-k。期望读取次数等于元素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)。

- user635541

---

注意：推导这个值的更简单方法是观察到只有一个x被检查，每个n-k个非x在所有x之前出现时都会被检查，这个概率是1/(k+1)。我们有1 + (n-k)/(k+1) = (n+1)/(k+1)。 - user635541

@user635541 谢谢你的结果。我确实考虑过对x进行排列组合。但是这样会产生多个相同数组的副本。因此，我决定不使用它们。你能解释一下使用k!的理由吗？另外，你能详细说明一下这个注释吗？我没太明白。抱歉。 - Brahadeesh

问题在于n!因子也会产生k!个相同数组的副本（假设非x元素是不同的）。 - user635541

@Brahadeesh 那么在i之前的元素呢？我们不应该也对它们进行排列吗？ - V K

我无法解决这个二项式求和问题，你能建议一种简化的方法吗？ - V K

你能解释一下，为什么将“Y中的元素y只有在它出现在X的每个元素之前时，才会被读取，而这种情况发生的概率是1/(k+1)”等同于Y中的元素被读取的概率是1/(k+1)吗？ - DDG

Answer 2

这里有一个使用Cormen术语的解决方案： 让S成为其他n-k个元素的集合。
让指示随机变量Xi=1，如果我们在执行过程中遇到了集合S的第i个元素。
Pr{Xi=1}=1/(k+1)，因此E[Xi]=1/(k+1)。
让指示随机变量Y=1，如果我们在执行过程中遇到了任何一个要搜索的k个元素之一。
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)。

- Avi Cohen

---

我个人觉得对于Y的解释有些令人困惑。如果对其他人有帮助的话，另一种思考方式是让X =（访问的不匹配元素数）和Y =（访问的匹配元素数）。那么，我们寻找Z =（访问的元素数）= X + Y，但是Y = 1的概率为1，所以E [X] = E [X] + E [Y] = E [X] + 1。 - Richard Fung