메르 센 트위스터의 시간 복잡도는 얼마입니까?

Question

나는 "메르 센 트위스터의 계산 복잡도는 O (p)입니다. 여기서 p는 다항식의 차수입니다."

• 이것은 무엇을 의미합니까?
• 이 다항식은 어떤 것을 의미합니까?
• 또한 계산 복잡도는 시간 복잡도를 나타내는 또 다른 방법입니까, 아니면 알고리즘이 실행되는 데 필요한 공간의 양과 관련이 있습니까? 2 N 난수들을 생성
는

Answer 1

N 난수를 생성하는만큼 회 걸리므 메르 센 트위스터의 시간 복잡도는 그것이 생성하는 것을 일정 시간이 걸리는 것을 의미한다 (1) O이고 단일 난수; Mersenne Twister는 일반적으로 대량의 난수를 계산하여 배치가 소비 될 때까지 한 번에 하나씩 임의의 숫자를 계산하여 더 많이 계산하므로 복잡도는 상각됩니다. 귀하가 참조하는 Google 검색은 상수를보다 정확하게 결정하려고 시도하지만 동일한 것을 말합니다. 전산 복잡성은 일반적으로 시간 복잡성을 의미하지만 일부 상황에서는 공간 복잡성을 나타낼 수도 있습니다.

Answer 2

generate 함수의 C 소스 코드를 원본 종이에서 보면 MT가 N-1 회 반복을 수행하는 두 개의 루프를 사용하여 한 번에 N 단어를 생성한다는 것을 알 수 있으며 각 루프는 고정 된 수의 산술 연산 또는 비트 연산입니다. 루프 이후 고정 된 수의 추가 연산/비트 연산이 수행됩니다. 결과적으로 generate은 생성 된 단어 당 상각 된 O (1) 시간 동안 N 단어를 생성하기 위해 O (N) 시간이 걸립니다.