Java的随机数生成器。 生成数字的复杂性

我知道Java使用线性同余生成器。 我的问题是 – 生成随机数的复杂性是多少？ 你如何进行这样的分析？

Answer 1

生成随机数的复杂性是O（1）。 你的意思是“它在运行时和内存方面的成本是多少”？

您可以使用微基准测量它们，例如junit-benchmark或Brent Boyer的Benchmark（参见最佳宏基准测试工具/框架的大量列表， 以测量Java中的单线程复杂算法？ ）。

此外，我认为Javas随机数生成器相当快，但统计上不好。 而是使用外部库，例如http://www.cs.gmu.edu/~sean/research/上的Mersenne Twister，或者，如果运行时对您来说非常重要，请使用Fast Mersenne Twister。

Answer 2

随机数发生器的时间复杂度为O（1）。 随着您拥有更多随机数，所需时间不会增加。

java.util.Random的随机性可能是个问题。 它使用2 ^ 48的种子，因此它会在这么多值之后重复。 这意味着nextLong（）不会生成所有可能的值。

如果这是一个问题，你可以使用SecureRandom，它比较慢，但它重复的点要高得多。

Answer 3

根据文档 ， java.util.Random.next实现如下：

  synchronized protected int next(int bits) { seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int)(seed >>> (48 - bits)); } 

没有任何东西需要花费不同的时间，但这在很大程度上是因为它只处理固定长度的数字。

所以这是Java的随机数生成器，它甚至不是随机数生成器，而是伪随机数生成器，而不是非常好的生成器，如上所述。

Answer 4

也许你可以尝试计算复杂性中的文本：Oded Goldreich的伪随机生成器

“ 生成的复杂性：典型的选择是生成器必须在多项式时间（其输入的长度 – 种子）中工作。其他选择也将被讨论。我们注意到在发生器上没有计算要求（或或者，提出非常温和的要求，例如双指数运行时上限），产生“发电机”，可以欺骗任何亚指数大小的电路系列。“