随机化序列算法分析

Two algorithms of randomize array of size n,

Algorithm A:

1. assign 1:n to array A of size n


2. step i=1:n-2


3. generate random number k ~ U[0, n-1-i]


4. B[i] = k


5. for j=k, n-2, A[j]=A[j+1]


6. repeat 2-5 on i

Algorithm B:

1. array A of 1:n


2. for i=0, n-1


3. generate k ~U[0, n-1]


4. swap A[i], A[k]

Algorithm A needs two array storage, averagely sum(1, (n-1)/2) assignments, that is (1+(n-1)/2)*(n-1)/2/2, leads to (n^2-1)/8, i.e. an O(n^2/8) algorithm.

Algorithm B needs one array storage, 2n assignments (n swaps), an O(2n) algorithm

Let n^2-1=8*2n, n approximates 16, i.e., when n <17, A is better, else, B is better