0
현재 반복없이 난수를 얻는 효율적인 방법을 조사 중입니다. 우리는 N-1로 번호 양식 0 모자를 가지고 우리가 K 번호는 무작위로 모자를 형성 걸릴정말 큰 범위에서 반복하지 않고 난수 생성
https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
: 문제를 이해하는 방법이 문서에 나와있는 예이다.
문제를 진술하는 더 공식적인 방법은 다음과 같습니다. k 위치의 벡터 공간이 주어지며 각 위치는 0과 n-1 사이의 정수를 가지며 벡터에는 반복이 없습니다. 우리는 균일 한 분포로 무작위로 요소를 들여다 볼 수 있기를 원합니다.
나는 이것을 수행하는 세 가지 방법으로 these을 발견했습니다. 저수지 샘플링에 대해서도 읽었습니다.
그러나 나는 n이 정말로 크고 k가 n보다 훨씬 작은 경우에 관심이 있습니다. 또한,이 상황에서도, O (k^2)에서 시간 복잡도를 갖는 알고리즘은 용인 될 수 없다. 반면에 n이 매우 클 경우, O (n)에서 공간 또는 시간 복잡성을 갖는 알고리즘을 수용 할 수 없습니다. 그래서 이것을 잘 수행 할 수있는 잘 알려진 알고리즘이 있는지 알고 싶습니다.
논문, 서적, 링크 등에 대한 언급은 모두 사과 할 것입니다. 그리고 어떤 종류의 조언이 필요합니다.
미리 감사드립니다.
추신 : 많은 비슷한 질문을했지만,이 경우 O (f (n))의 내용은 받아 들일 수 없습니다. 거의 모든 기능을 수행하는 f(). 매우 큰 공간 N에서 K 샘플을 생성
감사합니다. 이 알고리즘을 발견하고 그것을 언급하는 것을 잊어 버렸습니다. 문제는 : 해쉬 테이블이 O (k) 공간 (O (k) 시간을 우리가 초기화해야하기 때문에)을 어떻게 사용할 수 있는지 정확히 알지 못합니다. 충돌을 피하고자한다면, 테이블의 크기가 O (k)가되는 것이 좋습니까? –
구현 세부 사항은 실제 수치에 많이 의존하지만, 2k와 같은 크기의 해시 테이블은 최소한의 충돌을 가져야하며 간단한 선형 프로빙을 사용하더라도 매우 효율적이어야합니다. 왜 그렇게 생각하지 않습니까? –
안녕하세요. 나는 점근선 복잡성에 관심이있다. 나는 O (k) 크기의 테이블이 O (k) 시간 복잡성을 유지하기에 충분할 것인지를 묻는다. 나는 플로이드의 알고리즘과 다른 자료의 원본을 읽었지만 이것에 대한 증거를 찾을 수 없었다. 그래서 저는 시간 복잡성에 대해 회의적입니다. 자연스럽지 않으므로 적절한 증거를 찾고 싶습니다. –