Skip to content

随机函数

出处说明

本文内容摘自外部资源,为方便学员快速学习相关前置数学知识而整理在一起。内容可能较原文有删减,仅保留本课程所需的前置内容,以便学员快速掌握必备知识。

原文链接:https://oi-wiki.org/misc/random/

概述

要想使用随机化技巧,前提条件是能够快速生成随机数。本文将介绍生成随机数的常见方法。

随机数与伪随机数

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

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

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

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

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