问当A[i] != x时如何求P(Xi) =1/(k+1)的概率
EN

Stack Overflow用户

提问于 2019-10-10 15:49:58

回答 1查看 23关注 0票数 0

问题是：

现在考虑一种确定性线性搜索算法，我们称之为确定性搜索。具体地说，该算法按顺序在A中搜索x，考虑A1，A2；：；An，直到找到Ai =x或到达数组的末尾。假设输入数组的所有可能的排列都是相等的。

假设有k个>= 1索引i使得Ai = x，那么确定性搜索的平均运行时间是多少？

我不明白当Ai不等于x时如何得到P(Xi)，我知道P(min(p1，...，pk) > i) = P(p1 > i) * ... * P(pk > i) = (n-i) / n^k = A，那么为什么P(Xi)不等于A？

发布于 2019-10-10 18:49:26

假设在数组A中有n不同的值。因此，A中的值存在n!不同的排列。假设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。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/58317939

复制

相似问题

问当A[i] != x时如何求P(Xi) =1/(k+1)的概率EN