5

我试图得出确定性线性搜索算法的平均案例运行时间。该算法按照 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) 的简化。

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。X 中元素的总贡献为 |X| (1/k) = 1。

当且仅当它位于 X 的每个元素之前，即概率 1/(k+1) 时，才读取 Y 中的元素 y。Y中元素的总贡献是|Y| (1/(k+1)) = (nk)/(k+1)。

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

于 2011-02-26T13:30:06.993 回答
6

这是一个使用 Cormen 术语的解决方案：让S成为其他n-k元素的集合。
让指标随机变量Xi=1，如果我们在执行过程中遇到i集合的第 ' 个元素。因此. 如果我们在执行过程中遇到我们正在搜索的任何元素， 让指标随机变量。因此. 让随机变量是我们在执行过程中遇到的元素的总和。.S
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 回答