patternModerate
Classfication of randomized algorithms
Viewed 0 times
classficationrandomizedalgorithms
Problem
From Wikipedia about randomized algorithms
One has to distinguish between algorithms that use the random
input to reduce the expected running time or memory usage, but always
terminate with a correct result in a bounded amount of time, and
probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo
algorithms) or fail to produce a result (Las Vegas algorithms) either
by signalling a failure or failing to terminate.
input to reduce the expected running time or memory usage, but
always terminate with a correct result in a bounded amount of time?
fail to produce a result?
kind of randomized algorithms, and the other kind is those use the
random input to reduce the expected running time or memory usage,
but always terminate with a correct result in a bounded amount of
time?
One has to distinguish between algorithms that use the random
input to reduce the expected running time or memory usage, but always
terminate with a correct result in a bounded amount of time, and
probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo
algorithms) or fail to produce a result (Las Vegas algorithms) either
by signalling a failure or failing to terminate.
- I was wondering how the first kind of "algorithms use the random
input to reduce the expected running time or memory usage, but
always terminate with a correct result in a bounded amount of time?
- What differences are between it and Las Vegas algorithms which may
fail to produce a result?
- If I understand correctly, probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one
kind of randomized algorithms, and the other kind is those use the
random input to reduce the expected running time or memory usage,
but always terminate with a correct result in a bounded amount of
time?
Solution
-
An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.
-
This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.
-
These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.
There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.
An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.
-
This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.
-
These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.
There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.
Context
StackExchange Computer Science Q#6221, answer score: 12
Revisions (0)
No revisions yet.