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

Random.nextInt(n) uses Random.next() less than twice on average- it
uses it once,and if the value obtained is above the highest multiple
of n below MAX_INT it tries again,otherwise is returns the value
modulo n (this prevents the values above the highest multiple of n
below MAX_INT skewing the distribution),so returning a value which is
uniformly distributed in the range 0 to 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)

在旁注： –

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