Laz*_*zer 6 algorithm statistics probability
平均而言,查看数据库中的所有问题需要多少次点击？
这些问题需要什么方法？
这是一个数学问题而不是算法问题.正如sdcvvc所说,这是着名的优惠券收藏家的问题.
假设您有"收集"的问题.设X是表示所需点击次数的随机变量.如果我们将Xi定义为从我们(i-1)问题到我们有问题的那一刻的点击次数,那么:
X = X1 + X2 + ... + Xn
E(X)= E(X1 + X2 + ... + Xn)= EX1 + EX2 + ... + EXn
如果我们检查Xi,我们看到它实际上具有p =(n-i + 1)/ n的几何分布,因此平均值为n /(n-i + 1).因此:
EX = n*(1/n + 1 /(n-1)+ ... + 1/2 + 1/1)= n*Hn
其中Hn是第n个谐波数,可以用ln n近似:
EX~ = n*ln n
您可以运行简单的模拟并测试此近似值.