3

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

4

5 回答 5

3

这实际上取决于您对数组中数字的了解。如果它们都是从所有概率质量都在一个值上的分布中得出的，那么根据预期，您将需要 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

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

于 2011-01-15T20:23:15.730 回答
1

所说的问题是错误的。线性搜索可能会执行得更好。

于 2011-01-15T20:19:35.713 回答
1

虽然我认为 templatetypedef 有最有启发性的答案，但在这种情况下有一个更简单的答案。

考虑集合 {x1, x2, ..., xn} 的排列，其中 n = 2m。现在取一些你想要定位的元素 xi。对于 xi 出现在索引 m - k 处的每个排列，存在相应的镜像排列，其中 xi 出现在索引 m + k 处。这些可能指数的平均值只是 [(m - k) + (m + k)]/2 = m = n/2。因此，该集合所有可能排列的平均值为 n/2。

于 2011-01-16T22:02:01.197 回答
1

也许一个更简单的例子可以说明为什么平均值是 N/2：

假设您有一个包含 10 个项目的未排序数组： [5, 0, 9, 8, 1, 2, 7, 3, 4, 6]. 这是所有的数字[0..9]。

由于数组是未排序的（即您对项目的顺序一无所知），您可以在数组中找到特定项目的唯一方法是进行线性搜索：从第一项开始，直到找到您想要的重新寻找，或者你到达终点。

所以让我们计算一下找到每个项目需要多少操作。找到第一项 (5) 只需要一次操作。找到第二个项目 (0) 需要两个。找到最后一项 (6) 需要 10 次操作。找到所有 10 个项目所需的操作总数为 1+2+3+4+5+6+7+8+9+10，即 55。平均值为 55/10，即 5.5。

“线性搜索平均需要 N/2 步”传统智慧做出了许多假设。最大的两个是：

  1. 您要查找的项目在数组中。如果一个项目不在数组中，则需要 N 个步骤来确定。因此，如果您经常寻找不存在的项目，那么您每次搜索的平均步数将远高于 N/2。

  2. 平均而言，每个项目的搜索频率与任何其他项目大致相同。也就是说，您搜索“6”的频率与搜索“0”的频率相同，等等。如果某些项目的查找频率明显高于其他项目，那么每次搜索的平均步数将偏向于搜索频率更高的项目。该数字将高于或低于 N/2，具体取决于最常查找的项目的位置。

于 2011-01-15T21:29:04.323 回答
0

考虑一个简单的问题重新表述：

什么是极限

lim (i->inf) of (sum(from 1 to i of random(n)) /i)

或在 C 中：

int sum = 0, i;
for (i = 0; i < LARGE_NUM; i++) sum += random(n);
sum /= LARGE_NUM;

如果我们假设我们的值分布均匀（从到的random每个值都同样可能产生），那么预期结果将是。1n(1+n)/2

于 2011-01-15T20:24:57.787 回答