算法设计技巧与分析习题参考答案

复杂度分析如下:

每次随机生成一个新元素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) m?1m?1?n?m?1?k??k?1n?m?1且有

m?1T(n,m)?n?km?1?nkk?1n?k?k?1n?1?nm?1nm(m?1)n?1?k??2 k?1n?1因为m2

2T(n,m)??(m2)

14.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).