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

发布时间：2020-12-14 05:59:01 所属栏目：Java 来源：网络整理

导读：我想知道 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 ab

我想知道 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随机数生成器非常快,但统计上很糟糕)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!