我正在尝试推导确定性线性搜索算法的平均情况运行时间。该算法按顺序在未排序的数组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)。