随机化算法 学习笔记

Topic 1 ：随机函数

要想使用随机化技巧，前提条件是能够快速生成随机数。

随机数与伪随机数

说一个单独的数是「随机数」是无意义的，所以以下我们都默认讨论「随机数列」，即使提到「随机数」，指的也是「随机数列中的一个元素」。

现有的计算机的运算过程都是确定性的，因此，仅凭借算法来生成真正 不可预测、不可重复 的随机数列是不可能的。

然而在绝大部分情况下，我们都不需要如此强的随机性，而只需要所生成的数列在统计学上具有随机数列的种种特征（比如均匀分布、互相独立等等）。这样的数列即称为 伪随机数 序列。

随机数与伪随机数在实际生活和算法中的应用举例：

• 抽样调查时往往只需使用伪随机数。这是因为我们本就只关心统计特征。
• 网络安全中往往要用到（比刚刚提到的伪随机数）更强的随机数。这是因为攻击者可能会利用可预测性做文章。
• OI/ICPC 中用到的随机算法，基本都只需要伪随机数。这是因为，这些算法往往是 通过引入随机数 来把概率引入复杂度分析，从而降低复杂度。这本质上依然只利用了随机数的统计特征。
• 某些随机算法（例如 Moser 算法）用到了随机数的熵相关的性质，因此必须使用真正的随机数。