Science Fair Project Encyclopedia
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm which is correct; that is, it always produces the correct result. Thus, the random bits used only influence the resources used by the algorithm. A simple example is randomized quicksort, where the pivot is chosen randomly, but the result is always sorted. An alternative definition of a Las Vegas algorithm includes the restriction that the average-case running-time must be finite.
Compare to the Monte Carlo method where the resources used are constant, but the random bits influence if the result is correct.
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details