랜덤화 함수
Randomization function |
컴퓨터 과학에서 무작위화 함수 또는 무작위화 함수는 무작위화 알고리즘에서 사용하기에 적합한 두 특정 집합 사이에서 무작위로 선택한 함수를 구현하는 알고리즘이나 절차다.
무작위화 함수는 난수 생성기와 해시함수와 관련이 있지만 요구사항과 용도가 다소 다르며 구체적인 알고리즘이 필요한 경우가 많다.
사용하다
무작위화 함수는 임의 입력에 대해 기대 성능이 좋은 알고리즘을 임의 입력에 대해 동일한 성능을 갖는 알고리즘으로 전환하는 데 사용된다.
예를 들어, 퀵소트와 같은 정렬 알고리즘을 고려해 보자. 퀵소트는 입력 항목을 랜덤 순서로 표시할 때 예상 실행 시간은 적지만, 특정 불리한 순서로 표시될 때는 속도가 매우 느리다.정수 1에서 n까지의 무작위화 함수를 사용하여 해당 알고리즘을 호출하기 전에 "랜덤" 순서로 n 입력 항목을 재정렬할 수 있다.이 수정된(임의화된) 알고리즘은 입력 순서가 무엇이든 예상 실행 시간이 작을 것이다.
무작위성
이론적으로 무작위화 함수는 정말로 무작위로 가정되며 알고리즘이 실행될 때마다 예측할 수 없이 다른 함수를 산출한다.알고리즘을 실행할 때마다 무작위화 함수가 항상 동일한 매핑을 수행하거나 외부적으로 관측할 수 있는 일부 매개변수(프로그램의 시작 시간 등)에 의해 전적으로 결정된 매핑을 수행한다면 무작위화 기법은 작동하지 않을 것이다.그러한 "의사 임의화" 함수를 사용하면, 함수가 기본 결정론적 알고리즘에 대해 항상 "나쁜" 사례를 산출할 수 있도록 원칙적으로 일련의 호를 구성할 수 있다.그러한 일련의 통화의 경우, 무작위 입력에 대한 평균 비용보다는 평균 비용이 최악의 경우 비용에 더 가까울 것이다.
그러나 실무에서 주요 관심사는 결정론적 알고리즘에 대한 일부 "나쁜" 사례가 우연히 예측되는 것보다 훨씬 더 자주 실제로 발생할 수 있다는 것이다.예를 들어, 순진한 퀵소트 변종에서 최악의 경우는 입력 항목이 이미 정렬되었을 때인데, 이는 많은 애플리케이션에서 매우 흔한 일이다.그러한 알고리즘의 경우 고정된 의사 무작위 순열도 충분할 수 있다.결과적인 "의사 임의화" 알고리즘은 여전히 원본과 같은 많은 "나쁜" 사례를 가질 수 있지만, 그것들은 실제 적용에서 발생할 가능성이 상당히 낮은 특정한 주문일 것이다.따라서 실제로 사람들은 종종 사이비 무작위 숫자 생성기에서 파생되는 무작위화 함수를 사용하며, 프로그램의 시작 시간과 같은 외부 "랜덤" 데이터로 시드되는 것이 바람직하다.
균일성
랜덤화 함수에 대한 균일성 요건은 일반적으로 해시함수 및 유사랜덤 생성기의 요건에 비해 훨씬 약하다.최소 요건은 결정론적 알고리즘의 입력을 충분히 높은 확률의 "좋은" 입력에 매핑하는 것이다.(단, 랜덤화 함수가 각 가능한 매핑을 균일한 확률로 구현하는 경우 분석은 대개 더 간단하다.)
