SA
메인 내용으로 이동

Las Vegas Algorithm

A Las Vegas algorithm is a randomized algorithm that always produces a correct result or outputs that it has failed to find a solution. Randomness comes into play regarding the time taken to get a result. Unlike the Monte Carlo algorithms, which may produce incorrect results with a certain probability, a Las Vegas algorithm ensures that it is correct when it does have an impact.

An illustrative example is the Quickselect algorithm, a cousin of the Quicksort algorithm. Quickselect finds the kk-th smallest element of an unordered list. While it uses randomness to achieve its expected runtime, it always provides the correct element as an answer.

Interestingly, Las Vegas always gives the correct results but sometimes gives a very slow answer. You bet (risk) on time on the promise of accurate results—another exciting property in Computational Theory.

Monte Carlo and Las Vegas Algorithm