가중치 세트를 최대 1 개까지 추가했다고 가정 해 봅시다. 그리고 그 무게에 비례하는 길이의 일련의 상자를 만들기 위해 하나씩 줄 지어 서 있다고합니다. 각 bin에 줄의 자리에 해당하는 정수를 할당합니다.실제 회선 구간의 일정 시간 멤버십 인덱싱?
[0,1]에 어떤 숫자가 주어지면 어떤 숫자가이 숫자의 빈에 해당하는지 확인할 수 있기를 원합니다. 일정 시간 내에이를 수행하는 알고리즘을 생각해 낼 수 있습니까?
로그 시간 솔루션은 간단하지만 더 나은 것을 원합니다!
이것은 아마도 시간 O (1)의 이산 분포에서 무작위 샘플을 생성하는 데 사용할 수있는 alias method을 사용하여 수행 할 수 있습니다. 이 알고리즘을 적용하여 변형을 단순히 반전시켜 균일 무작위 변수에서 이산 버킷으로 매핑하는 대신 불연속 버킷에서 균일 변수로 매핑 할 수 있다고 생각합니다. 거기에서 값이 속하는 버킷을 결정할 수 있습니다.
희망이 있습니다.
EDIT : 저는 최근에 별칭 방법 및 기타 관련 트릭에 대한 광범위한 글을 썼습니다. 다행히도 알고리즘과 직관이 더 명확하고 쉽게 만들어집니다!
내 실제 작업은 정확히 당신이 암시 한 것입니다. 주의 깊게 읽어야합니다 :) – duckworthd
k 개의 항목이있는 표를 만들고 1/k는 가장 작은 항목보다 작아야합니다. 그런 다음 테이블이 가리키는 위치에 항목을 채운 다음 O (1)을가집니다.
k에 대한 제한을 완화하면 첫 번째 단계는 위와 같지만 두 번째 단계는 선형 또는 로그 검색 인 다단계 조회를 만들 수 있습니다. 그러면 O(log2(n/k))이됩니다. n/k, k=n => O(log2(1)) = O(1)?
사용할 테이블의 항목을 찾으려면 바닥 (x * k)
첫 번째 제안은 1/p에 비례하는 메모리를 필요로합니다. 여기서 p는 가장 작은 확률입니다. 메모리 요구 사항은 임의적으로 나쁠 수 있습니다. 나는 두 번째 스키마를 따르지 않는다. 어떻게 k를 선택 하나? – duckworthd
매우주의해야합니다. reals로 인덱싱하는 것은 위험합니다. 왜냐하면'[0,1]'의 모든 숫자를 정확하게 표현할 수 없기 때문입니다. – zneak
대수는 엄청난 양의 데이터가 없다면 거의 일정한 시간이라는 것을 기억하십시오. log_2 (1000) = 10, log_2 (10^6) = 20. –