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）時間。