1
我已经读过“梅森扭转者的计算复杂度为O（p ）其中p是多项式的次数”。梅森扭纹机的时间复杂度是多少？
- 这是什么意思？
- 这是指哪一个多项式？
- 此外，计算复杂度是说时间复杂度的另一种方式，还是这与算法运行所需的空间量有关？
A
回答
3
生成2 Ñ随机数，只要需要两倍产生ñ随机数，所以Mersenne扭曲的时间复杂度是O（1），这意味着它需要的时间的恒定量，以产生单个随机数;请注意，这可能是分期偿还的复杂性，因为Mersenne Twister通常会计算一批随机数，然后一次将它们分派出去，直到批量消耗完毕，此时计算得更多。你所引用的谷歌搜索是说同样的事情，虽然它试图更准确地确定常数。计算复杂度一般是指时间复杂度，尽管在某些情况下也可能涉及空间复杂度。
2
如果您在原始论文中查看generate函数的C源代码，您会看到MT一次生成N个字，使用总共进行N-1次迭代的两个循环，并且内部的计算每个循环都是固定数量的算术或位运算。在循环之后，执行固定数量的附加算术/按位操作。因此，generate需要O（N）时间来产生N个单词，以产生每个单词的分期O（1）时间。