梅森捻线机的时间复杂度是多少？

Question

我读过“梅森扭曲器的计算复杂度是 O(p ² )，其中 p 是多项式的次数”。

• 这是什么意思？
• 这是指哪个多项式？
• 另外，计算复杂度是时间复杂度的另一种说法，还是与算法运行所需的空间量有关？

Answer 1

生成 2 n 个随机数的时间是生成n个随机数的两倍，因此 Mersenne Twister 的时间复杂度为 O(1)，意味着生成单个随机数需要恒定的时间；请注意，这可能是摊销的复杂性，因为 Mersenne Twister 通常计算一批随机数，然后一次分发一个，直到该批被消耗，此时它计算更多。您引用的 Google 搜索也在说同样的事情，尽管它试图更精确地确定常数。计算复杂度通常是指时间复杂度，尽管在某些情况下它也可以指空间复杂度。