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

Question

This question从有限集合中获取随机值让我思考......

人们想要从一组 Y 值中检索 X 唯一值是相当普遍的。例如，我可能想处理一副牌中的一手牌。我想要 5 张卡片，而且我希望它们都是独一无二的。

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

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

(问题不是:“我怎样才能改进它？”因为它相对容易修复，而且我确信它在其他地方已经多次讨论过。)

Answer 1

变量

= 集合中的项目总数
米 = 要从 n 个项目的集合中检索的唯一值的数量
d(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。为了理解这一点，画一个 decision tree 很有帮助。 .两次选择了一个非唯一项目，我们有可能再次选择它。这导致将 (1/n)3 添加到步骤 i=1 中的总预期尝试次数。每次我们选错号码时，都有可能再次选错号码。这导致:

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

类似地，在一般的第 i:th 步骤中，在一次选择中选错项目的机会是 i/n，导致:

d(i) = 1 + i/n + (i/n) ² + (i/n) ³ + (i/n) ⁴ + ... =
= sum( (i/n) ^k ), where k ∈ [0,∞]

这是一个 geometric sequence因此很容易计算它的总和:

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

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

T(m,n) = sum ( d(i) ), where 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)

可能(并且可能)通过使用某种技术来评估序列而不是通过(项数)*(最大项)的粗略方法来建立稍微严格的上限

结论

这意味着大 O 订单是 O(m*n/(n-m+1)) .我认为没有可能的方法来简化这个表达式。

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