Я читал, что «вычислительная сложность вихря Мерсенна равна O (p2), где p — степень многочлена».
Генерация 2 n случайных чисел занимает в два раза больше времени, чем генерация n случайных чисел, поэтому временная сложность Вихря Мерсенна составляет O(1), то есть требуется постоянное количество время генерации одного случайного числа; обратите внимание, что это, вероятно, амортизированная сложность, поскольку Mersenne Twister обычно вычисляет пакет случайных чисел, а затем распределяет их по одному, пока пакет не будет использован, после чего он вычисляет больше. Поиск Google, на который вы ссылаетесь, говорит то же самое, хотя и пытается более точно определить константу. Вычислительная сложность обычно относится к временной сложности, хотя в некоторых контекстах она также может относиться к пространственной сложности.
Если вы посмотрите на исходный код C для функции generate в их оригинальной статье, вы увидите, что MT генерирует N слов за раз, используя два цикла, которые в сумме составляют N-1 итераций, и что вычисления в каждом цикле представляют собой фиксированное количество арифметических или побитовых операций. После циклов выполняется фиксированное количество дополнительных арифметических/побитовых операций. Следовательно, generate требуется O(N) времени для создания N слов, при амортизированном O(1) времени на каждое сгенерированное слово.
