News for hackers. Stuff that matters.
Re:Cache Eviction: When Are Randomized Algorithms Better Tha... by kccqzy on Monday February 18, 2019 @02:25AM (#19189102)
Randomization can really do wonders at times. There are some algorithms for which the most efficient algorithm is essentially using randomness in a clever way. The Miller–Rabin primality test comes to mind. Or the randomized minimum cut problem. And even when deterministic algorithms have the same big-O asymptotic complexity as randomized algorithms, the randomized ones often perform better due to simpler code. Treap vs red-black tree is a classic example.

There are no comments on this comment yet.