我想知道
java.util.Random.next(n)是否与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随机数生成器非常快,但统计上很糟糕)
