我想知道 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 .(这是一个外部库，用于衡量运行时的复杂性，因为 Java 的随机数生成器非常快，但在统计上很糟糕)
关于java - 什么是 java.util.Random.next(n) 的 O(n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20764300/