算法高级教程2.3SherwoodAlgorithms.pptVIP

* * Consider the problem of selecting a sample of m elements randomly from a set of n elements,where mn. For simplicity, we will assume that the elements are positive integers between 1 and n. Namely Input: Two positive integers m,n with mn. Output: An array a[1..m] of m distinct positive integers selected randomly from the set {1,2,…,n}. Randomized sampling * Consider the following selection method. First mark all the n elements as unselected. Next, repeat the following step until exactly m elements have been selected. Generate a random number r between 1and n. If r is marked unselected,then mark it selected and add it to the sample. This method is described more precisely in Algorithm RandomizedSampling. Where, s[1..n] is a boolean array indicating whether an integer has been selected. * RandomSampling(s,m) 1 for i←1 to n do 2 ???????? s[i]←false 3??? k ← 0 4??? while km do 5?????????? r ← Randomi(1,n) 6?????????? if not s[r] then 7 ????????????? k ← k+1 8 ????????????? a[k] ← r 9 ????????????? s[r] ← true * Definition Let c be a coin whose probability of “heads” is p,and let q=1-p. Suppose we flip c repeatedly until “heads” appears for the first time,Let X be the random variable denoting the total number of flips until “heads” appears for the first time. Then X is said to have the geometric distribution with probability * The expected value of X is * Theorem The expected running time of the algorithm is Θ(n). Proof. Let pk be the probability of generating an unselected integer given that k-1 numbers have already been selected,where 1≤k≤m. Clearly, * Let Xk, 1≤k≤m be the random variable denoting the number of integers generated in order to select the k-th integer,then Xk has the geometric distribution with expected value * Let Y be the random variable denoting the total number of integers generated in order to select the m out of n integers. By linearity of expectation, we have Hence, * Due to Since