algorithm - 梅森捻线器的时间复杂度是多少？

Question

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

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

Answer 1

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

Answer 2

如果您查看generate原始论文中该函数的 C 源代码，您会发现 MT 使用两个循环一次生成 N 个单词，总共 N-1 次迭代，并且每个循环内的计算都是固定的算术或按位运算的数量。在循环之后执行固定数量的附加算术/按位运算。因此，generate生成 N 个单词需要 O(N) 时间，每个单词生成的平均时间为 O(1)。