有限集中的朴素随机选择的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)².要理解这一点,绘制决策树会很有帮助.选择两次非独特项目后,我们有可能再次这样做.这导致在步骤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)⁴ + ... =
= 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.即我们需要m次尝试独立于n,因为没有碰撞.