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