我想知道是否java.util.Random.next(n)
与n线性比例或是一个常数吗?有人可以帮我这个或者告诉我如何确定复杂性?
来自文档:
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随机数生成器非常快,但统计上很糟糕)
Javadoc next
解释道
该方法
next
由Random类通过原子方式更新种子来实现
(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
并返回
(int)(seed >>> (48 - bits))
显然,这些表达式中没有O(n)复杂性的痕迹.