随机函数
出处说明
本文内容摘自外部资源,为方便学员快速学习相关前置数学知识而整理在一起。内容可能较原文有删减,仅保留本课程所需的前置内容,以便学员快速掌握必备知识。
概述
要想使用随机化技巧,前提条件是能够快速生成随机数。本文将介绍生成随机数的常见方法。
随机数与伪随机数
说一个单独的数是「随机数」是无意义的,所以以下我们都默认讨论「随机数列」,即使提到「随机数」,指的也是「随机数列中的一个元素」。
现有的计算机的运算过程都是确定性的,因此,仅凭借算法来生成真正 不可预测、不可重复 的随机数列是不可能的。
然而在绝大部分情况下,我们都不需要如此强的随机性,而只需要所生成的数列在统计学上具有随机数列的种种特征(比如均匀分布、互相独立等等)。这样的数列即称为 伪随机数 序列。
随机数与伪随机数在实际生活和算法中的应用举例:
- 抽样调查时往往只需使用伪随机数。这是因为我们本就只关心统计特征。
- 网络安全中往往要用到(比刚刚提到的伪随机数)更强的随机数。这是因为攻击者可能会利用可预测性做文章。
- OI/ICPC 中用到的随机算法,基本都只需要伪随机数。这是因为,这些算法往往是 通过引入随机数 来把概率引入复杂度分析,从而降低复杂度。这本质上依然只利用了随机数的统计特征。
- 某些随机算法(例如 Moser 算法)用到了随机数的熵相关的性质,因此必须使用真正的随机数。