arrays - 为什么在数组中查找项目的平均步骤数为 N/2？

Question

有人可以解释为什么在未排序的数组数据结构中查找项目的平均步骤数是 N/2 吗？

Answer 1

这实际上取决于您对数组中数字的了解。如果它们都是从所有概率质量都在一个值上的分布中提取的，那么根据期望，您将需要恰好 1 步才能找到您正在寻找的值，因为每个值都是相同的，例如。

现在让我们做一个非常有力的假设，数组中充满了不同值的随机排列。您可以将其视为选择一些任意排序的不同元素列表，然后随机排列它。在这种情况下，假设您正在搜索数组中实际存在的某个元素(如果该元素不存在，则此证明无效)。那么你需要走的步数由 X 给出，其中 X 是数组中元素的位置。平均步数为 E[X]，由

给出

E[X] = 1 Pr[X = 1] + 2 Pr[X = 2] + ... + n Pr[X = n]

由于我们假设所有元素都是从随机排列中抽取的，

Pr[X = 1] = Pr[X = 2] = ... = Pr[X = n] = 1/n

所以这个表达式由

E[X] = sum (i = 1 to n) i / n = (1 / n) sum (i = 1 to n) i = (1 / n) (n)(n + 1) / 2
     = (n + 1) / 2

我认为这就是您正在寻找的答案。