랜덤화 알고리즘 (Randomized Algorithm)

랜덤화 알고리즘 (Randomized Algorithm)

알고리즘 수행 과정에서 난수(Random Number)를 사용하여 결정을 내리는 알고리즘으로, 확률적 분석에 기반하여 평균적으로 우수한 성능을 달성

분류

• •Las Vegas: 항상 정확한 결과 보장, 실행 시간이 확률적. 예: Randomized QuickSort(기대 O(n log n))
• •Monte Carlo: 실행 시간 보장, 결과의 정확도가 확률적. 예: Miller-Rabin 소수 판별(오류 확률 ≤ (1/4)^k)

기대 시간복잡도: 최악 입력에 대해서도 난수화로 평균적 성능 보장, 적대적(adversarial) 입력 무력화

적용: QuickSort(랜덤 피벗/최악 O(n²) 회피), Miller-Rabin(소수 판별), Min-Cut(Karger 알고리즘), 해시 함수(Universal Hashing)

장점: 최악 경우 회피, 구현 단순, 적대적 입력 대응

단점: 결과 비결정적(Monte Carlo), 난수 품질 의존, 분석 복잡

비교: 결정적 알고리즘(항상 동일 결과/최악 보장) vs Las Vegas(정확/시간 확률적) vs Monte Carlo(시간 보장/정확도 확률적)

연관: 확률론, 퀵 정렬, 해시, 근사 알고리즘, 암호학