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

)?1n+1n?1n?n(n-1)?n?1C(n?2)?1n???n1?n?1?n(n-1)?n(n-1)???n?1C(n?2)?1n???111?n?1?n-1?n-1?n???n?1C(n?2)?2n?n?1?1n?1C(n?2)?2n?1?n?1?1n?1??n-2+n-1?n-2C(n-3)???2n?1?n?1(n?1)(n?2)?(n?1)(n?1)(n?1)(n?2)C(n?3)?2?n-12?n?1n?1???(n-1)(n-2)+(n-1)(n-2)???n?2C(n?3)?222?n?n?1???1?n-2+n-2-n-1???1n?2C(n?3)?3n?2?n?1n?2C(n?3)(*)C(n(*)

1n?1C(n)??C(n?1)nn2n?1??C(n?2)n?1n?13n?1??C(n?3)n?2n?24n+1?+C(n-4)n-3n-3?...n?1n?1 ??C(1)22n?1n?1??//{QC(1)?1}22?n(可将C(n)=n代入推导过程，以验证其正确性) 因此，随机化拟二分

查找的时间复杂度为O(n)，二分查找的时间复杂度为O(logn)。随机化方法的效率反而比二分查找低，其原因在于…

14.10 设L=x1,x2,…,xn是一个元素序列，其中元素x恰好出现k次（1≤k≤n），我们要找到一个j，使得xj=x。考虑重复执行下面的过程直到找到x 为止。生成一个1到n之间色随机数i，并检查是否xi=x。在平均情况下，这种方法和线性方法查找哪一种方法快？请说明。 解：

(1) 随机查找的情况

不妨设第i1,i2,…,ik个元素等于x，记I={i1,i2,…,ik}, |I|=k, 则P{i∈I}=k/n，记p=k/n, q=1-p，则查找长度的数学期望 E(ASL)=p×1+q×p×2+…+qi-1×p×i+…=1/p=n/k

(2) 线性查找的情况

kkkkkkE(ASL)??1?(1?)??2?(1?)?(1?)??3?...nnn?1nn?1n?2kkkk?(1?)?(1?)?...?(1?)??(n?k)nn?1k?2k?1kkkk?(1?)?(1?)?...?(1?)?(1?)?1?(n?k?1)nn?1k?2k?1n?k?1kkkk??(1?)?(1?)?...?(1?)??inn?1n?i?2n?(i?1)i?1其中，分母=n(n-1)(n-2)…(n-i+1)=n!/(n-i)!

分子=(n-k)( n-k-1)…(n-k-i+2)×k×i=(n-k)!×k×i /(n-k-i+1)! 则通项可写为