我读到“梅森扭曲器的计算复杂度为 O(p2)，其中 p 是多项式的次数”。
- 这是什么意思？
- 这是指哪个多项式？
- 此外，计算复杂度是时间复杂度的另一种表述方式，还是与算法运行所需的空间量有关？
最佳答案
生成 2 n 个随机数所花的时间是生成 n 个随机数的两倍，因此 Mersenne Twister 的时间复杂度为 O(1)，这意味着它需要生成单个随机数的时间恒定；请注意，这可能是摊销的复杂性，因为 Mersenne Twister 通常会计算一批随机数，然后一次分发一个，直到这批随机数被消耗掉，此时它会计算更多。您引用的谷歌搜索说的是同一件事，尽管它试图更精确地确定常量。计算复杂度通常是指时间复杂度，但在某些情况下它也可以指空间复杂度。
关于algorithm - Mersenne twister 的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25651532/