On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu
wrote:
So let's improve on that: whenever an element is found in
position k, pick a random number i in the range 0, 1, 2, ..., k
inclusive. Then swap the array elements at indexes i and k.
This is the Randomized Slide to Front strategy.
With RStF, worst case search time remains O(n), as is the
unsuccessful search. However, frequently searched elements
migrate quickly to the front - it only takes O(log n) searches
to bring a given value at the front of the array.
Something is wrong with the math here. The randomization means
that you must assume that you get element k-1 in the worst case,
so if you repeatedly search for the same element you need O(N)
repeats to move it to the front, so you get O(N^2) complexity for
moving any element to the front.
Right?
You are probably thinking about the average case analysis, which
is a more sensible theoretical concept for randomized algorithms
than worst case, but then you need a model for what is typical.
