从有限集中进行朴素随机选择的 O 值是多少？

Question

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

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

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

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

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

Answer 1

变量

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)²。 为了理解这一点，绘制一个决策树会很有帮助。 两次选择一个非唯一的项目后，我们有可能会再次选择它。 这会导致步骤 i=1 中的总预期尝试次数增加 (1/n)³。 每次我们选错号码时，我们都有可能再次选错号码。 结果是：

d(1) = 1 + 1/n + (1/n)² + (1/n)³ + (1/n)⁴ + ...

类似地，在一般的第 i: 步中，一次选择中选错项目的机会是 i/n，结果是：

d(i) = 1 + i/n + ( i/n)² + (i/n)³ + (i/n)⁴ + ... =
= 总和( (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 次尝试，因为没有碰撞。

Answer 2

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

<前><代码>(yi)/y。

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

<前><代码>y/(yi)。

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

<前><代码> y/y + y/(y-1) + ... + y/(y-x+1)

这可以使用谐波数表示为

y（H_y - H_yx）。

从维基百科页面您可以得到近似值

H_x = ln(x) + gamma + O(1/x)

因此，从一组 y 元素中挑选 x 个唯一元素所需的试验次数
是

y (ln(y) - ln(yx)) + O(y/(yx))。 
  

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

Answer 3

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

因此，如果您从一组 n 个值中提取 m 个值，则第一个值将要求您最多提取 1 个值才能获得唯一值。 第二个最多需要 2 个（您看到第一个值，然后是一个唯一值），第三个需要 3，...第 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) 抽奖。

这等于 [1 + i/n] 从 i=0 到 (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 是列表的大小。

Answer 4

有一个漂亮的 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) 记忆。

Answer 5

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

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

编辑：经过一番思考后，这是我的尝试：

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

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

Answer 6

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

答案：N * H_N，其中 H_N 是第 N 个 谐波数，

著名的近似值 log(N)。

这意味着所讨论的算法是N log N。

举个有趣的例子，如果您滚动一个普通的 6 面骰子，直到看到每个数字之一，则需要花费平均 6 H₆ = 14.7 卷。

Answer 7

在详细回答这个问题之前，让我们先定义一下框架。 假设您有一个包含 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)，但常数更高）。

Answer 8

大多数人忘记了，如果号码已经跑完，查找也需要一段时间。

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

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)< 的下界/code> 尝试和性能 O(n^2) 或 O(n*ln(n))。

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