12

这个关于从有限集中获取随机值的问题让我思考......

人们想要从一组 Y 值中检索 X 个唯一值是很常见的。例如，我可能想从一副牌中发一手牌。我想要 5 张卡片，我希望它们都是独一无二的。

现在，我可以天真地做到这一点，随机选择一张卡片 5 次，每次我得到重复的卡片时再试一次，直到我得到 5 张卡片。但是，对于来自大型集合的大量值，这并不是很好。例如，如果我想从一组 1,000,000 中获得 999,999 个值，那么这种方法会变得非常糟糕。

问题是：有多糟糕？我正在找人来解释 O() 值。获得第 x 个数字将需要 y 次尝试......但是有多少？我知道如何计算出任何给定值，但是有没有一种直接的方法可以将其推广到整个系列并获得 O() 值？

（问题不是：“我怎样才能改进它？”因为它相对容易修复，而且我确信它已经在其他地方多次介绍过。）

4

8 回答 8

5

变量

n = 集合中的项目总数
m = 要从 n 个项目的集合中检索的唯一值的数量
d(i) = 在步骤 i 中实现某个值所需的预期尝试次数
i = 表示一个具体步骤。i ∈ [0, n-1]
T(m,n) = 使用朴素算法从一组 n 个项目中选择 m 个唯一项目的预期总尝试次数

推理

第一步，i=0，是微不足道的。无论我们选择哪个值，我们都会在第一次尝试时得到一个独特的值。因此：

d(0) = 1

在第二步中，i=1，我们至少需要 1 次尝试（我们选择有效唯一值的尝试）。最重要的是，我们有可能选择了错误的值。这个机会是（先前选择的物品数量）/（物品总数）。在这种情况下为 1/n。如果我们选择了错误的物品，我们有 1/n 的机会再次选择错误的物品。将其乘以 1/n，因为这是我们两次选择错误的组合概率，得到 (1/n) 2。要理解这一点，绘制决策树会很有帮助。选择了两次非独特物品后，我们很有可能会再次选择。这导致添加 (1/n) 3到步骤 i=1 中的总预期尝试次数。每次我们选错号码时，我们都有可能再次选错号码。这导致：

d(1) = 1 + 1/n + (1/n) 2 + (1/n) 3 + (1/n) 4 + ...

同样，在一般的第 i:th 步中，一次选择中选择错误项目的机会是 i/n，导致：

d(i) = 1 + i/n + (i/n) 2 + (i/n) 3 + (i/n) 4 + ... =
= sum( (i/n) k )，其中 k ∈ [0,∞]

这是一个几何序列，因此很容易计算它的总和：

d(i) = (1 - i/n) -1

然后通过对每个步骤中的预期尝试次数求和来计算总体复杂度：

T(m,n) = sum ( d(i) )，其中 i ∈ [0,m-1] =
= 1 + (1 - 1/n) -1 + (1 - 2/n) -1 + ( 1 - 3/n) -1 + ... + (1 - (m-1)/n) -1

将上述级数中的分数扩大 n，我们得到：

T(m,n) = n/n + n/(n-1) + n/(n-2) + n/(n-3) + ... + n/(n-m+2) + n /(n-m+1)

我们可以使用以下事实：

n/n ≤ n/(n-1) ≤ n/(n-2) ≤ n/(n-3) ≤ ... ≤ n/(n-m+2) ≤ n/(n-m+1 )

由于该系列有 m 个项，并且每个项都满足上面的不等式，我们得到：

T(m,n) ≤ n/(n-m+1) + n/(n-m+1) + n/(n-m+1) + n/(n-m+1) + ... + n/(n-m+1) + n/(n-m+1) =
= m*n/(n-m+1)

通过使用某种技术来评估系列，而不是通过（项数）*（最大项）的粗略方法来建立一个稍微严格的上限，这可能（并且可能）是可能的

结论

这意味着 Big-O 顺序是O(m*n/(n-m+1))。我看不出有什么办法可以简化这个表达式。

回顾结果以检查它是否有意义，我们看到，如果 n 是常数，并且 m 越来越接近 n，结果将迅速增加，因为分母变得非常小。这就是我们所期望的，例如，如果我们考虑问题中给出的关于从一组 1,000,000 中选择 999,999 个值的示例。如果我们改为让 m 为常数并且 n 变得非常非常大，那么复杂性将在 n → ∞ 的极限内收敛于 O(m)。这也是我们所期望的，因为在从“接近”无限大小的集合中选择恒定数量的项目时，选择先前选择的值的概率基本上是 0。即，我们需要独立于 n 的 m 次尝试，因为没有碰撞。

于 2009-08-18T20:36:22.097 回答
4

如果您已经选择了 i 个值，那么您从一组 y 值中选择一个新值的概率为

(y-i)/y.

因此，获得第 (i+1) 个元素的预期试验次数为

y/(y-i).

因此，选择 x 唯一元素的预期试验次数是总和

 y/y + y/(y-1) + ... + y/(y-x+1)

这可以使用谐波数表示为

y (H y - H y-x )。

从维基百科页面你得到近似值

H x = ln(x) + 伽马 + O(1/x)

因此，从一组 y 元素中挑选 x 个唯一元素的必要试验次数为

y (ln(y) - ln(y-x)) + O(y/(y-x)).

如果需要，您可以通过对 H x使用更精确的近似值来获得更精确的近似值。特别是当 x 较小时，可以大大改善结果。

于 2009-08-18T17:40:06.273 回答
3

如果您愿意假设您的随机数生成器总是会在循环回到给定抽奖的先前看到的值之前找到一个唯一值，那么这个算法是 O(m^2)，其中 m 是唯一的数量您正在绘制的值。

因此，如果您从一组 n 值中提取 m 值，则第一个值将要求您最多绘制 1 以获得唯一值。第二个最多需要 2 个（您会看到第一个值，然后是唯一值），第三个 3，... 第 m 个 m。因此，您总共需要 1 + 2 + 3 + ... + m = [m*(m+1)]/2 = (m^2 + m)/2 次抽奖。这是 O(m^2)。

如果没有这个假设，我不确定你如何保证算法会完成。很有可能（尤其是使用可能有循环的伪随机数生成器），您将一遍又一遍地看到相同的值，而永远不会得到另一个唯一值。

==编辑==

对于一般情况：

在您的第一次抽奖中，您将进行 1 次抽奖。在您的第二次抽奖中，您预计会中奖 1（成功抽奖）+ 1/n（“部分”抽奖，代表您重复抽奖的机会） 在第三次抽奖中，您希望抽中 1（成功抽奖）+ 2/n（“部分”抽奖...）...在您的第 m 次抽奖中，您希望进行 1 + (m-1)/n 次抽奖。

因此，在平均情况下，您将进行 1 + (1 + 1/n) + (1 + 2/n) + ... + (1 + (m-1)/n) 次抽签。

这等于从 i=0 到 [1 + i/n] 的 (m-1) 的总和。让我们表示 sum(1 + i/n, i, 0, m-1)。

然后：

sum(1 + i/n, i, 0, m-1) = sum(1, i, 0, m-1) + sum(i/n, i, 0, m-1)
                        = m + sum(i/n, i, 0, m-1)
                        = m + (1/n) * sum(i, i, 0, m-1)
                        = m + (1/n)*[(m-1)*m]/2
                        = (m^2)/(2n) - (m)/(2n) + m

我们去掉低阶项和常数，我们得到这是 O(m^2/n)，其中 m 是要绘制的数字，n 是列表的大小。

于 2009-08-18T14:02:15.417 回答
2

该算法的最坏情况显然是当您选择完整的 N 个项目时。这相当于问：平均而言，在每面至少出现一次之前，我必须掷 N 面骰子多少次？

答案：N * H N，其中 H N是第 N次谐波数，

替代文字
一个著名的近似值log(N)。

这意味着有问题的算法是N log N。

举个有趣的例子，如果你掷一个普通的 6 面骰子，直到你看到每个数字中的一个，平均需要掷 6 H 6 = 14.7 次。

于 2009-10-20T22:09:09.737 回答
2

你的实际问题实际上比我回答的更有趣（而且更难）。我从来都不擅长统计（而且我已经有一段时间没有做过了），但直观地说，我会说该算法的运行时复杂度可能类似于指数。只要选择的元素数量与数组的大小相比足够小，碰撞率就会小到接近线性时间，但在某些时候，碰撞的数量可能会快速增长并且运行-时间将付诸东流。

如果您想证明这一点，我认为您必须根据所需的元素数量对预期的碰撞次数做一些适度聪明的事情。也可以通过归纳来实现，但我认为走这条路需要比第一种选择更聪明。

编辑：经过深思熟虑，这是我的尝试：

给定一个元素数组m，并寻找n随机和不同的元素。那么很容易看出，当我们想要选择第ith 个元素时，选择我们已经访问过的元素的几率是(i-1)/m。这就是该特定选择的预期碰撞次数。对于拾取n元素，预期的碰撞次数将是每个拾取的预期碰撞次数的总和。我们将其代入 Wolfram Alpha (sum (i-1)/m, i=1 to n) 并得到答案(n**2 - n)/2m。我们的朴素算法的平均选择数是n + (n**2 - n)/2m。

除非我的记忆完全让我失望（实际上这完全有可能），否则这会给出平均情况下的运行时间O(n**2)。

于 2009-08-18T13:50:24.667 回答
2

有一个漂亮的 O(n) 算法。它如下。假设你有 n 个项目，你想从中挑选 m 个项目。我假设函数 rand() 产生一个介于 0 和 1 之间的随机实数。这是算法：

items_left=n
items_left_to_pick=m
for j=1,...,n
    if rand()<=(items_left_to_pick/items_left)
        Pick item j
        items_left_to_pick=items_left_to_pick-1
    end
    items_left=items_left-1
end

可以证明该算法确实以相等的概率选择了 m 个项目的每个子集，尽管证据并不明显。不幸的是，我目前没有参考资料。

编辑这个算法的优点是它只需要 O(m) 内存（假设这些项目只是整数或者可以即时生成）与使用 O(n) 内存的洗牌相比。

于 2009-08-18T13:51:15.150 回答
0

在能够详细回答这个问题之前，让我们定义框架。假设您有 n 个不同对象的集合 {a1, a2, ..., an}，并希望从该集合中挑选 m 个不同对象，这样给定对象 aj 出现在结果中的概率对于所有对象都是相等的.

如果你已经选择了 k 个项目，并且从完整的集合 {a1, a2, ..., an} 中随机选择一个项目，那么该项目之前没有被选择过的概率是 (nk)/n。这意味着在获得新对象之前必须采取的样本数是（假设随机抽样的独立性）与参数 (nk)/n的几何关系。因此，获得一个额外项目的预期样本数为 n/(nk)，如果 k 与 n 相比较小，则接近 1。

结论，如果你需要 m 个唯一的对象，随机选择，这个算法给你

n/n + n/(n-1) + n/(n-2) + n/(n-3) + .... + n/(n-(m-1))

正如 Alderath 所示，可以通过以下方式估计

m*n / (n-m+1)。

你可以从这个公式中看到更多： * 随着已经选择的对象数量的增加，获得一个新的唯一元素的预期样本数量也会增加（这听起来很合乎逻辑）。* 当 m 接近 n 时，您可以期待非常长的计算时间，尤其是当 n 很大时。

为了从集合中获得 m 个唯一成员，请使用David Knuth 算法的变体来获得随机排列。在这里，我假设 n 个对象存储在一个数组中。

for i = 1..m
  k = randInt(i, n)
  exchange(i, k)
end

在这里，randInt 从 {i, i+1, ... n} 中采样一个整数，并交换翻转数组的两个成员。您只需要洗牌 m 次，因此计算时间为 O(m)，而内存为 O(n)（尽管您可以调整它以仅保存条目，例如 a[i] <> i，这将你在时间和内存上都是 O(m)，但常数更高）。

于 2009-08-24T12:15:40.917 回答
0

大多数人忘记了查找，如果数字已经运行，也需要一段时间。

如前所述，必要的尝试次数可以通过以下方式评估：

T(n,m) = n(H(n)-H(n-m)) ⪅ n(ln(n)-ln(n-m))

这n*ln(n)适用于有趣的价值m

但是，对于这些“尝试”中的每一个，您都必须进行查找。这可能是一个简单的O(n)遍历，或者类似于二叉树的东西。这将为您提供n^2*ln(n)或的总性能n*ln(n)^2。

对于较小的m( ) 值，您可以使用- 不等式m < n/2进行非常好的近似，从而得出以下公式：T(n,m)HA

2*m*n/(2*n-m+1)

至于m，这给出了尝试和性能或n的下限。O(n)O(n^2)O(n*ln(n))

然而，所有结果都比我预期的要好得多，这表明该算法在许多非关键情况下实际上可能很好，您可以接受偶尔更长的运行时间（当您不走运时）。

于 2010-01-30T22:01:03.393 回答