#3-4-2 The Art of Computer Programming - 준수치적 알고리즘

이번 절은 무작위 표본추출 및 뒤섞기다.

 

N개의 레코드를 담음 파일에서 무작위로 n개의 레코드를 편향되지 않게 선택할 때 사용됨.

예를 들어 품질 관리(QA) 등 표본 추출이 필요한 경우 이 이론이 사용될 수 있음.

 

가장 명백한 접근은 각 레코드를 확률 n/N으로 선택하는 것임.

 

전통적인 카드 섞기랑 유사한 부분이 존재한다고 한다.

52장짜리 카드 한 벌이 균등 분포의 10%에 도달하기 위해서는 리플 섞기를 적어도 7번,

무작위 리플의 경우 14회면 10%에 도달할 수 있다고 함.

 

t가 작을 때는 상관없지만 t가 클 때는 무작위 순열을 얻는데 시간이 좀 걸린다.

 

오늘은 여기까지