3
$\begingroup$

I was comparing the original Fisher-Yates shuffle vs the modern Fisher-Yates shuffle.

This reduces the algorithm's time complexity to O(n), compared to O(n2) for the naive implementation.

Ok I cannot understand how is it that we have n2 for the original algorithm.

You see, our first trip is to write out the random numbers. So that's 1N. and then the second step is to write out the elements based on the N. so that's 2N total?

Or is it like something to do with the second step takes longer so it's more N ?

  • 0
    "The second step is to write out the elements based on N" - I don't understand at all what you're talking about here. The algorithm is basically "pick a random number $k\le m$, cross out the $k$-th unstruck number" (which requires counting through many numbers), repeated over and over again for $m=n,n-1,\dots,3,2,1$.2011-08-20

2 Answers 2

7

The crucial difference between the two algorithms is described in the sentence before the one you quoted:

Whereas a naive computer implementation of Fisher and Yates' method would spend needless time counting the remaining numbers in step 3 above, Durstenfeld's solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration.

This allows you to use the random numbers directly as indices into an array, which takes only constant time per selection, and thus $O(n)$ in total; whereas if you leave the array unchanged, or if you use a linked list and unlink the used elements, you have to count through to the selected numbers, which takes $O(n)$ time per selection, and thus $O(n^2)$ in total.

1

The original version of the algorithm picks $n$ random integers $X_i$, for $i=1$ to $n$, with $1 \leq X_i \leq (n+1-i)$. At stage $i$ the number of "move to next position" steps is at least $(X_i - 1)$, where the motion is iteration through an array or a linked list. The expected number of those steps is at least $\Sigma E[(X_i - 1)] = \Sigma ((i+1)/2 - 1) = \Sigma (i-1)/2 = n(n-1)/4 = O(n^2)$.

  • 0
    @joriki : yes, "i" was intended in the second and third sums. Thank you. Also, $i$ in the first sum runs from 1 to N which corresponds to going from N to 1 in the second and third sums.2011-08-20