3 ms·
Nope. Thats really the point - if we find the best deterministic algorithm, it means we have found the one with the best deterministic running time. By loosenin
by zaptheimpaler 13y ago
Nope. Thats really the point - if we find the best deterministic algorithm, it means we have found the one with the best deterministic running time. By loosening our criteria of running time to expected running time and allowing randomness, we can sometimes do better than deterministic algorithms.
- TeMPOraL 13y agoIt doesn't square well with my intuition - if we understand how allowing randomness improves expected running time, then surely we must be able to create a deterministic algorithm that is at least as good as the randomized one. Am I missing some critical piece of understanding here?
- ethbro 13y agoI'd expect that it's simply that the additional constraints implied by requiring deterministic behavior precludes certain optimizations that can lead to improved running time. Iow, if you can never do X, then you cannot write any algorithm that may do X.
- zaptheimpaler 13y agoWell keep in mind that the inputs to the algorithm can vary. Randomization can help avoid a bad input from throwing your algorithm off. A simple example of how randomization helps is quicksort: if we pick the pivot to always be the first element, then any sorted array will cause worst-case running time. But by randomizing the pivot, we can do well (in expectation) for any input.