（随机选择的另一种分析方法）在这个问题中，我们用指示器随机变量来分析RANDOMIZED-SELECT，这一方法类似于对随机快排的分析方法。
与快速排序中的分析一样，我们假设所有的元素都是互异的，输入数组A的元素被重命名为z1,z2,...,zn，其中zi是第i小的元素。因此，调用RANDOMIZED-SELECT(A,1,n,k)返回zk。
对所有
，设
Xijk=I{在执行算法查找zk期间，zi与zj进行过比较}
a.给出E[Xijk]的准确表达式。（提示：你的表达式可能有不同的值，依赖于i,j,k的值。）
b.设Xk表示在找到zk时A中元素的总比较次数，证明：
c.证明：
d.假设A中的元素都是互异的，证明：RANDOMIZED-SELECT的期望运行时间是O(n)。
int Randomized_Select(A, p, r, i) {
int q, k;
if (p == r)
return A[p];
q = Randomized_Partition(A, p, r);
k = q-p+1;
if (i == k)
return A[q];
else if (i < k)
return Randomized_Select(A, p, q-1, i);
else
return Randomized_Select(A, q+1, r, i-k);
} 
