정수 스트림의 최대 및 최소

Question

정수 스트림 (한 번만 통과 할 수 있음)이 주어지면 최대 및 최소값을 찾는 최상의 솔루션은 무엇입니까? 각 숫자를 처리 할 수있는 충분한 시간이있는 경우 가장 쉬운 해결책은 별도의 변수에 최소값과 최대 값을 유지하는 것입니다.하지만 모든 단일 값을 처리 할 수없는 경우 가장 좋은 방법은 무엇입니까? 최대 및 최소 변수를 유지하고 매초마다 예를 들어 건너 뛰는 것보다 더 좋은 해결책이 있습니까?

Answer 1

실제 최대 값과 최소값을 원하면 변수를 사용하여이를 추적하십시오.

입력 데이터에 따라 확률 론적 최소/최대 값이 "충분히 정확함"일 수 있습니다. 따라서 50 % 확률로 모든 수를 살펴 본다면 정확한 최소 또는 최대 값을 가질 확률이 50 %에 불과할 것입니다. 하지만 아마도 이미 두 번째로 큰/최소 등을 가질 확률은 75 %입니다. 그러나 샘플링을 수행 할 난수를 계산하는 것은 이미 최소/최대 모든 숫자를 보는 것보다 비용이 많이 듭니다. 1 초마다 건너 뛰는 것은 위험합니다. 데이터에 짝수/홀수 패턴이있어 심하게 망칠 수 있습니다.