复杂度分析如下:

每次随机生成一个新元素r，要查找r是否已经出现在已经选定的数字中。

设生成第i个有效随机数时，平均要产生E(Xi)次, 则复杂度

T(n,m)?0?E(X1)?1?E(X2)?...?(m?1)?E(Xm)??(k?1)?E(Xk)k?1mmn??(k?1)?n?(k?1)k?1n??k?n?kk?1容易证明，

m?1

kkT(n,m)?n??n?k?1n?kk?1n?(m?1)m?1nnm(m?1) ?k???n?m?1k?1n?m?12m?1m?1且有

m?1kkT(n,m)?n??n?k?1n?kk?1n?1nm?1nm(m?1) ?k???n?1k?1n?12m?1因为m

222

214.16 另解：算法设计思路如下:

生成一个[1,n]之间的随机数r，互换X[n]和X[r]； 再生成一个[1,n-1]之间的随机数r，互换X[n-1]和X[r]；… 再生成一个[1,n-m+1]之间的随机数r，互换X[n-m+1]和X[r]；

返回X[n-m+1…n]，即为随机选择的m个数。 好处：不需要重复产生随机数；不需要额外空间。 1. for i←n downto n-m+1 2. r← random(1,i) 3. X[r]←→X[i] 4. end for

5. return X[n-m+1…n]

时间复杂度：?(m). 空间复杂度：?(1).