发布时间 : 星期五 文章算法设计技巧与分析习题参考答案更新完毕开始阅读af57e4f5b4daa58da1114a4b
复杂度分析如下:
每次随机生成一个新元素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).