(n?k)!?ki(n?k)!(n?i)!?k?(k?1)!(n?k?i?1)!???in!/(n?i)!n!(n?k?i?1)!?(k?1)!iC(n?k)!(n?i)!k!??i?n!(n?k?i?1)!(k?1)!Ck?1n?ikn
于是，
n?k?1?i?1iCCk?1n?iknn?1?k?1
可以证明上式的成立。事实上，上式等价于
n?k?1i?1?iCk?1n?in?1k(n?1)n!k?1kk?1?Cn??Cn?C?C?1nn k?1(k?1)k!(n?k)!n?k?1即要证明
?i?1k?1kk?1iCn?C?C?inn成立。思路：右边变换→左边形式
C?C?C?Cknk?1n?1k?1n?1k?1n?1?C?C?C?C?Ckn?1k?1n?2k?1n?2?C?C?C?Ckn?2k?1n?3?Ckn?3?...
Ck?1n?C?Ckn?1k?1n?1k?1n?1kn?2k?1n?2k?1n?2kn?3k?1n?3k?1n?3?...?C?...?Ckk?1kk?1k?1k，另一方面
?Ck?1k?1?C?C?C?...?C?C，(*) 其中
kkCCCkn?1kn?2???Ck?1n?2?Ck?1n?3?...?Ck?1k?Ck?1k?1
Ck?1n?3?...?CCk?1k?C?Ck?1k?1kk?1k?1kk?1k?1
C?kkCk?1k?1将以上各式(除了*式)相加，即可得到
kk?1k?1k?1k?1k?1Cn?Cn=Cn?2C?3C?...?(n?k?1)C?1n?2n?3k?1?n?k?1i?1n?k?1?i?1k?1iCn?i
iC?即有
k?1n?i?C?Cknk?1n成立。
总结：随机查找
E(ASL)?n，线性查找E(ASL)?n?1kk?1，
n?1nk?nk?1?k?k(k?1)?0，故线性查找更快。
因为14.16 修改14.7节的随机抽样算法，使得它不再需要布尔数组S[1…n]，假设n比m大得多，比如n>m.
解：算法设计如下: 1. k←1
2. while k≤m
3. r←random(1,n) 4. i←k-1
5. while i≥1 and r≠A[i] 6. i←i-1 7. end while 8. if i=0 9. A[k]←r 10. k←k+1 11. end if 12. end while
2
