3 ms·
> I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a
by PartiallyTyped 4y ago
> I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a 10- or 100-times more complicated solution
We tend to use "Las Vegas" and "Monte Carlo" to classify randomised algorithms, where the former means using randomness to get a speedup, and the latter means using randomness to get an approximately correct solution.
An example of the former is QuickSort, where we shuffle the elements, giving the Expected nlogn time complexity* . An example of the latter is bloom filters. Other examples are found all over approximation algorithms like taking random cuts off graphs.
* Assuming something like Yates shuffling with O(N) complexity is used.
- chii 4y agoand once in a while, the shuffle puts the elements in a pattern that makes quicksort perform worst case (n^2). But i guess that is rare, the larger the list! So in practice, it works.
- PartiallyTyped 4y agoThe larger the list it gets exponentially less likely that this occurs if the shuffling occurs at every iteration. We have 2/(n!) probability that the shuffle sorts the list either way. The probability that it happens on the second level is 2/((n-1)!). So the probability that it happens twice is 4/(1^2 * 2^2 … (n-1)^2 * n) Which ends up being prod_{i=1} ^N i ^ i It’s so astronomically unlikely, that it just never does.