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

Question

我想知道 java.util.Random.next(n) 是否与 n 成线性关系还是一个常数？有人可以帮我解决这个问题，或者告诉我如何确定复杂性吗？

Answer 1

来自文档:

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 的随机数生成器非常快，但在统计上很糟糕)