问题：
现在考虑一个确定性的线性搜索算法，我们称之为 确定性搜索。具体来说，该算法按顺序搜索 A 的 x， 考虑 A[1]、A[2];: : : ;A[n]，直到它找到A[i] = x或到达数组的末尾。假设输入数组的所有可能排列的可能性相等。
假设有 k 个>= 1 个索引 i，使得 A[i] = x。确定性搜索的平均运行时间是多少？
我很困惑当 A[i] 不等于 x 时如何获得 P(Xi(。我知道 P(min(p1,..., pk(> i( = P(p1> i( * ... * P(pk> i( = [(n-i(/n]^k = A，那么为什么 P(Xi( 不等于 A？
假设你在数组A中n不同的值。因此，n!中的值存在不同的排列A.假设A[1] == x，这意味着您将通过一次比较找到它。现在，首先计算x排列的数量。(n-1)!适用于其他 n-1 位置。因此，A[1] == x的概率是(n-1)!/n! = 1/n.
现在，尝试为第二个地方计算相同的东西。它将再次1/n(因为首先的相同分析在这里有效(。但是您需要两个比较才能找到x。
因此，预期的比较数量是sum_{i=1}^n i*1/n = 1*1/n + 2*1/n + ... + n*1/n = (1+2+...+n)/n = (n+1)/2。