本文主要是介绍算法导论学习（一）——概率分析和随机算法【待续】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 球与箱子问题（礼券收集者问题）：
有b个箱子，每投一次球，球等可能地落到每个箱子中，问，投多少次球，才能使每个箱子都至少有一个球？
【补充知识】
① 几何分布的概念：假定我们有一系列伯努利试验，其中每一个的成功率为p，失败率为q=1-p。在获得一次成功前要进行多少次实验？如果在第k次成功，对于k>=1，Pr{X=k}=q^(k-1)*p。
一个满足上述式子的分布称为几何分布。
期望是1/p，方差是q/(p^2).
② 调和级数
设所需投球的数学期望为n，可以把n次投球分为n个阶段，第i个阶段包括第i-1次命中到第i次命中之间的投球，用ni表示。对第i阶段的每次投球，得到一次命中的概率是(b-i+1)/b。
于是E(ni)=b/(b-i+1)
因此我们有：
所以，在我们期望每个箱子里都有一个球之前，大约要投b(lnb)次。
2 特征序列
这篇关于算法导论学习（一）——概率分析和随机算法【待续】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
