我读到,“Melsern捻线机的计算复杂度是O(P2),其中p是多项式的程度”。
这意味着什么?
这是指哪个多项式?
另外,计算复杂性是说时间复杂度的另一种方式,或者这与算法运行所需的空间量有关吗?
最佳答案
生成2个N个随机数是生成N个随机数的两倍,所以Melsern捻器的时间复杂度为O(1),这意味着需要一个恒定的时间来生成单个随机数;注意这可能是已摊销的复杂性。由于mersenne twister通常计算一批随机数,然后一次一个地将它们分发出去,直到该批被消耗,此时它计算更多。你引用的google搜索也在说同样的话,尽管它试图更精确地确定常数。计算复杂性通常是指时间复杂度,但在某些情况下,它也可以指空间复杂度。