什么是java.util.Random.next(n)的O(n)

Question

我想知道是否java.util.Random.next(n)与n线性比例或是一个常数吗？有人可以帮我这个或者告诉我如何确定复杂性？

Answer 1

来自文档:

Random.nextInt(n)使用的Random.next()平均少于两次 - 它使用一次,如果获得的值高于MAX_INT以下n的最高倍数,它再次尝试,否则返回模数n(这个防止高于MAX_INT低于分布的n的最高倍数的值,因此返回一个均匀分布在0到n-1范围内的值.

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

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

所以复杂性是O(1)

在旁注: -

您可以使用多种工具来测量微基准测试的复杂性.你可以在这里找到一个清单.但是,如果运行时复杂性对您很重要,您可以使用Fast Mersenne Twister.(这是一个外部库来测量运行时复杂性,因为Javas随机数生成器非常快,但统计上很糟糕)

Answer 2

Javadoc next解释道

该方法next由Random类通过原子方式更新种子来实现

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

并返回

(int)(seed >>> (48 - bits))

显然,这些表达式中没有O(n)复杂性的痕迹.