Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 21
Текст из файла (страница 21)
For this algorithm andmany other randomized algorithms, no particular input elicits its worst-case behavior. Evenyour worst enemy cannot produce a bad input array, since the random permutation makes theinput order irrelevant. The randomized algorithm performs badly only if the random-numbergenerator produces an "unlucky" permutation.For the hiring problem, the only change needed in the code is to randomly permute the array.RANDOMIZED-HIRE-ASSISTANT(n)1 randomly permute the list of candidates2 best ← 0→ candidate 0 is a least-qualified dummy candidate3 for i ← 1 to n4do interview candidate i5if candidate i is better than candidate best6then best ← i7hire candidate iWith this simple change, we have created a randomized algorithm whose performancematches that obtained by assuming that the candidates were presented in a random order.Lemma 5.3The expected hiring cost of the procedure RANDOMIZED-HIRE-ASSISTANT is O(ch ln n).Proof After permuting the input array, we have achieved a situation identical to that of theprobabilistic analysis of HIRE-ASSISTANT.The comparison between Lemmas 5.2 and 5.3 captures the difference between probabilisticanalysis and randomized algorithms.
In Lemma 5.2, we make an assumption about the input.In Lemma 5.3, we make no such assumption, although randomizing the input takes someadditional time. In the remainder of this section, we discuss some issues involved in randomlypermuting inputs.Randomly permuting arraysMany randomized algorithms randomize the input by permuting the given input array. (Thereare other ways to use randomization.) Here, we shall discuss two methods for doing so.
Weassume that we are given an array A which, without loss of generality, contains the elements 1through n. Our goal is to produce a random permutation of the array.One common method is to assign each element A[i] of the array a random priority P[i], andthen sort the elements of A according to these priorities. For example if our initial array is A =<1, 2, 3, 4> and we choose random priorities P = <36, 3, 97, 19>, we would produce an arrayB = <2, 4, 1, 3>, since the second priority is the smallest, followed by the fourth, then the first,and finally the third.
We call this procedure PERMUTE-BY-SORTING:PERMUTE-BY-SORTING(A)1 n ← length[A]2 for i ← 1 to n3do P[i] = RANDOM(1, n3)4 sort A, using P as sort keys5 return ALine 3 chooses a random number between 1 and n3. We use a range of 1 to n3 to make it likelythat all the priorities in P are unique. (Exercise 5.3-5 asks you to prove that the probabilitythat all entries are unique is at least 1 - 1/n, and Exercise 5.3-6 asks how to implement thealgorithm even if two or more priorities are identical.) Let us assume that all the priorities areunique.The time-consuming step in this procedure is the sorting in line 4. As we shall see in Chapter8, if we use a comparison sort, sorting takes Ω(n lg n) time. We can achieve this lower bound,since we have seen that merge sort takes Θ(n lg n) time.
(We shall see other comparison sortsthat take Θ(n lg n) time in Part II.) After sorting, if P[i] is the jth smallest priority, then A[i]will be in position j of the output. In this manner we obtain a permutation. It remains to provethat the procedure produces a uniform random permutation, that is, that every permutation ofthe numbers 1 through n is equally likely to be produced.Lemma 5.4Procedure PERMUTE-BY-SORTING produces a uniform random permutation of the input,assuming that all priorities are distinct.Proof We start by considering the particular permutation in which each element A[i] receivesthe ith smallest priority.
We shall show that this permutation occurs with probability exactly1/n!. For i = 1, 2, ..., n, let Xi be the event that element A[i] receives the ith smallest priority.Then we wish to compute the probability that for all i, event Xi occurs, which isPr {X1 ∩ X2 ∩ X3 ∩ ··· ∩ Xn-1 ∩ Xn}.Using Exercise C.2-6, this probability is equal toPr {X1} · Pr{X2 | X1} · Pr{X3 | X2 ∩ X1} · Pr{X4 | X3 ∩ X2 ∩ X1}Pr{Xi | Xi-1 ∩ Xi-2 ∩ ··· ∩ X1} Pr{Xn | Xn-1 ∩ ··· ∩ X1}.We have that Pr {X1} = 1/n because it is the probability that one priority chosen randomly outof a set of n is the smallest. Next, we observe that Pr {X2 | X1} = 1/(n - 1) because given thatelement A[1] has the smallest priority, each of the remaining n - 1 elements has an equalchance of having the second smallest priority.
In general, for i = 2, 3, ..., n, we have that Pr{Xi | Xi-1 ∩ Xi-2 ∩ ··· ∩ X1} = 1/(n - i + 1), since, given that elements A[1] through A[i - 1] havethe i - 1 smallest priorities (in order), each of the remaining n - (i - 1) elements has an equalchance of having the ith smallest priority. Thus, we haveand we have shown that the probability of obtaining the identity permutation is 1/n!.We can extend this proof to work for any permutation of priorities. Consider any fixedpermutation σ = <σ(1), σ(2), ..., σ(n)> of the set {1, 2, ..., n}.
Let us denote by ri the rank ofthe priority assigned to element A[i], where the element with the jth smallest priority has rankj. If we define Xi as the event in which element A[i] receives the σ(i)th smallest priority, or ri =σ(i), the same proof still applies. Therefore, if we calculate the probability of obtaining anyparticular permutation, the calculation is identical to the one above, so that the probability ofobtaining this permutation is also 1/n!.One might think that to prove that a permutation is a uniform random permutation it sufficesto show that, for each element A[i], the probability that it winds up in position j is 1/n.Exercise 5.3-4 shows that this weaker condition is, in fact, insufficient.A better method for generating a random permutation is to permute the given array in place.The procedure RANDOMIZE-IN-PLACE does so in O(n) time.
In iteration i, the element A[i]is chosen randomly from among elements A[i] through A[n]. Subsequent to iteration i, A[i] isnever altered.RANDOMIZE-IN-PLACE(A)1 n ← length[A]2 for i ← to n3do swap A[i] ↔ A[RANDOM(i, n)]We will use a loop invariant to show that procedure RANDOMIZE-IN-PLACE produces auniform random permutation. Given a set of n elements, a k-permutation is a sequencecontaining k of the n elements. (See Appendix B.) There are n!/(n - k)! such possible kpermutations.Lemma 5.5Procedure RANDOMIZE-IN-PLACE computes a uniform random permutation.Proof We use the following loop invariant:•Just prior to the ith iteration of the for loop of lines 2-3, for each possible (i - 1)permutation, the subarray A[1 ..
i - 1] contains this (i - 1)-permutation with probability(n - i + 1)!/n!.We need to show that this invariant is true prior to the first loop iteration, that each iteration ofthe loop maintains the invariant, and that the invariant provides a useful property to showcorrectness when the loop terminates.••Initialization: Consider the situation just before the first loop iteration, so that i = 1.The loop invariant says that for each possible 0-permutation, the sub-array A[1 .. 0]contains this 0-permutation with probability (n - i + 1)!/n! = n!/n! = 1. The subarrayA[1 ..
0] is an empty subarray, and a 0-permutation has no elements. Thus, A[1 .. 0]contains any 0-permutation with probability 1, and the loop invariant holds prior to thefirst iteration.Maintenance: We assume that just before the (i - 1)st iteration, each possible (i - 1)permutation appears in the subarray A[1 .. i - 1] with probability (n - i + 1)!/n!, and wewill show that after the ith iteration, each possible i-permutation appears in thesubarray A[1 ..
i] with probability (n - i)!/n!. Incrementing i for the next iteration willthen maintain the loop invariant.Let us examine the ith iteration. Consider a particular i-permutation, and denote theelements in it by <x1, x2, ..., xi>. This permutation consists of an (i - 1)-permutation<x1, ..., xi-1> followed by the value xi that the algorithm places in A[i]. Let E1 denotethe event in which the first i - 1 iterations have created the particular (i - 1)permutation <x1,..., xi-1> in A[1 .. i - 1]. By the loop invariant, Pr {E1} = (n - i + 1)!/n!.Let E2 be the event that ith iteration puts xi in position A[i]. The i-permutation <x1, ...,xi> is formed in A[1 .. i] precisely when both E1 and E2 occur, and so we wish tocompute Pr {E2 ∩ E1}. Using equation (C.14), we havePr {E2 ∩ E1} = Pr{E2 | E1}Pr{E1}.The probability Pr {E2 | E1} equals 1/(n-i + 1) because in line 3 the algorithm choosesxi randomly from the n - i + 1 values in positions A[i ..
n]. Thus, we have•Termination: At termination, i = n + 1, and we have that the subarray A[1 .. n] is agiven n-permutation with probability (n - n)!/n! = 1/n!.Thus, RANDOMIZE-IN-PLACE produces a uniform random permutation.A randomized algorithm is often the simplest and most efficient way to solve a problem. Weshall use randomized algorithms occasionally throughout this book.Exercises 5.3-1Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questionswhether it is true prior to the first iteration. His reasoning is that one could just as easilydeclare that an empty subarray contains no 0-permutations.
Therefore, the probability that anempty subarray contains a 0-permutation should be 0, thus invalidating the loop invariantprior to the first iteration. Rewrite the procedure RANDOMIZE-IN-PLACE so that itsassociated loop invariant applies to a nonempty subarray prior to the first iteration, andmodify the proof of Lemma 5.5 for your procedure.Exercises 5.3-2Professor Kelp decides to write a procedure that will produce at random any permutationbesides the identity permutation. He proposes the following procedure:PERMUTE-WITHOUT-IDENTITY(A)1 n ← length[A]2 for i ← 1 to n3do swap A[i] ↔ A[RANDOM(i + 1, n)]Does this code do what Professor Kelp intends?Exercises 5.3-3Suppose that instead of swapping element A[i] with a random element from the subarray A[i ..n], we swapped it with a random element from anywhere in the array:PERMUTE-WITH-ALL(A)1 n ← length[A]2 for i ← 1 to n3do swap A[i] ↔ A[RANDOM(1, n)]Does this code produce a uniform random permutation? Why or why not?Exercises 5.3-4Professor Armstrong suggests the following procedure for generating a uniform randompermutation:PERMUTE-BY-CYCLIC(A)1 n ← length[A]2 offset ← RANDOM(1, n)3 for i ← 1 to n4do dest ← i + offset5if dest > n6then dest ← dest -n7B[dest] ← A[i]8 return BShow that each element A[i] has a 1/n probability of winding up in any particular position inB.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
