라스베가스 알고리즘

라스베가스 알고리즘은 무작위 알고리즘이다. 답을 내면 항상 맞는 답이고, 못 찾으면 못 찾았다고 말한다. 무작위인 건 결과가 아니라 걸리는 시간이다. 특정 확률로 틀린 결과를 낼 수도 있는 몬테카를로 알고리즘과 달리, 라스베가스 알고리즘은 정확한 결과를 보장한다.

퀵소트 알고리즘의 변형인 퀵셀렉트가 좋은 예이다. 퀵셀렉트는 정렬되지 않은 목록에서 $k$번째로 작은 요소를 찾는다. 기대 실행 시간을 얻으려고 무작위성을 쓰지만, 정답으로 내놓는 요소는 항상 맞다.

재밌는 건 추산치의 값은 매우 정확한데, 아주 낮은 확률로 시간이 엄청나게 오래 걸린다는 것이다. 정확도를 약속받는 대신 시간에 리스크를 거는 셈이다. 계산 이론에서 재밌는 지점이다.

Monte Carlo and Las Vegas Algorithm