algorithm - CLRS - 随机搜索 - 如何计算预期的选秀次数？

Question

这是 CLRS 问题。问题来自 CLRS 书的第三版:5-2-b。

随机搜索是一种算法，您必须随机选择一个元素并将其与搜索到的元素进行比较。如果等于，我们需要停止。现在，假设您正好有一个索引为 i 的元素，使得 A[i]=x(x 是数组中的搜索元素)。在找到 x 之前，我们必须选择 A 中的索引的预期数量是多少？另外，当我们有超过 1 个等于 x 的索引值时，我们如何找到预期的索引数？

Answer 1

我们可以定义一个随机变量 X = 选择目标元素之前的迭代次数。如果您概括术语，将“迭代”称为“试验”，将“选择目标元素”称为“成功”，则 X = 成功前的试验次数。

这个随机变量有一个众所周知的分布。这是一个geometric distribution给定成功概率参数 p。几何分布的期望值为 E(X) = 1/p。

要将几何分布应用于问题，必须确定成功概率 p。对于只有一个索引包含目标值的情况，p = 1/n 其中 n 是搜索集合的大小。所以在这种情况下，E(X) = n。

对于任意数量的索引映射到目标值的一般情况，p = m/n 其中 m 是映射到目标值的索引的数量。所以在这种情况下 E(X) = n/m。