Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 19
Текст из файла (страница 19)
We therefore concentrate on analyzing mch, the hiringcost. This quantity varies with each run of the algorithm.This scenario serves as a model for a common computational paradigm. It is often the casethat we need to find the maximum or minimum value in a sequence by examining eachelement of the sequence and maintaining a current "winner." The hiring problem models howoften we update our notion of which element is currently winning.Worst-case analysisIn the worst case, we actually hire every candidate that we interview.
This situation occurs ifthe candidates come in increasing order of quality, in which case we hire n times, for a totalhiring cost of O(nch).It might be reasonable to expect, however, that the candidates do not always come inincreasing order of quality. In fact, we have no idea about the order in which they arrive, nordo we have any control over this order. Therefore, it is natural to ask what we expect tohappen in a typical or average case.Probabilistic analysisProbabilistic analysis is the use of probability in the analysis of problems.
Most commonly,we use probabilistic analysis to analyze the running time of an algorithm. Sometimes, we useit to analyze other quantities, such as the hiring cost in procedure HIRE-ASSISTANT. Inorder to perform a probabilistic analysis, we must use knowledge of, or make assumptionsabout, the distribution of the inputs.
Then we analyze our algorithm, computing an expectedrunning time. The expectation is taken over the distribution of the possible inputs. Thus weare, in effect, averaging the running time over all possible inputs.We must be very careful in deciding on the distribution of inputs. For some problems, it isreasonable to assume something about the set of all possible inputs, and we can useprobabilistic analysis as a technique for designing an efficient algorithm and as a means forgaining insight into a problem.
For other problems, we cannot describe a reasonable inputdistribution, and in these cases we cannot use probabilistic analysis.For the hiring problem, we can assume that the applicants come in a random order. What doesthat mean for this problem? We assume that we can compare any two candidates and decidewhich one is better qualified; that is, there is a total order on the candidates. (See Appendix Bfor the definition of a total order.) We can therefore rank each candidate with a uniquenumber from 1 through n, using rank(i) to denote the rank of applicant i, and adopt theconvention that a higher rank corresponds to a better qualified applicant. The ordered list<rank(1), rank(2), ..., rank(n)> is a permutation of the list <1, 2, ..., n>.
Saying that theapplicants come in a random order is equivalent to saying that this list of ranks is equallylikely to be any one of the n! permutations of the numbers 1 through n. Alternatively, we saythat the ranks form a uniform random permutation; that is, each of the possible n!permutations appears with equal probability.Section 5.2 contains a probabilistic analysis of the hiring problem.Randomized algorithmsIn order to use probabilistic analysis, we need to know something about the distribution on theinputs.
In many cases, we know very little about the input distribution. Even if we do knowsomething about the distribution, we may not be able to model this knowledgecomputationally. Yet we often can use probability and randomness as a tool for algorithmdesign and analysis, by making the behavior of part of the algorithm random.In the hiring problem, it may seem as if the candidates are being presented to us in a randomorder, but we have no way of knowing whether or not they really are. Thus, in order todevelop a randomized algorithm for the hiring problem, we must have greater control over theorder in which we interview the candidates.
We will, therefore, change the model slightly. Wewill say that the employment agency has n candidates, and they send us a list of thecandidates in advance. On each day, we choose, randomly, which candidate to interview.Although we know nothing about the candidates (besides their names), we have made asignificant change. Instead of relying on a guess that the candidates will come to us in arandom order, we have instead gained control of the process and enforced a random order.More generally, we call an algorithm randomized if its behavior is determined not only by itsinput but also by values produced by a random-number generator.
We shall assume that wehave at our disposal a random-number generator RANDOM. A call to RANDOM(a, b)returns an integer between a and b, inclusive, with each such integer being equally likely. Forexample, RANDOM(0, 1) produces 0 with probability 1/2, and it produces 1 with probability1/2. A call to RANDOM(3, 7) returns either 3, 4, 5, 6 or 7, each with probability 1/5. Eachinteger returned by RANDOM is independent of the integers returned on previous calls. Youmay imagine RANDOM as rolling a (b - a + 1)-sided die to obtain its output.
(In practice,most programming environments offer a pseudorandom-number generator: a deterministicalgorithm returning numbers that "look" statistically random.)aExercises 5.1-1Show that the assumption that we are always able to determine which candidate is best in line4 of procedure HIRE-ASSISTANT implies that we know a total order on the ranks of thecandidates.Exercises 5.1-2:Describe an implementation of the procedure RANDOM(a, b) that only makes calls toRANDOM(0, 1).
What is the expected running time of your procedure, as a function of a andb?Exercises 5.1-3:Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At yourdisposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with someprobability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is.Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiasedanswer, returning 0 with probability 1/2 and 1 with probability 1/2.
What is the expectedrunning time of your algorithm as a function of p?5.2 Indicator random variablesIn order to analyze many algorithms, including the hiring problem, we will use indicatorrandom variables. Indicator random variables provide a convenient method for convertingbetween probabilities and expectations. Suppose we are given a sample space S and an eventA. Then the indicator random variable I {A} associated with event A is defined as(5.1)As a simple example, let us determine the expected number of heads that we obtain whenflipping a fair coin.
Our sample space is S = {H, T}, and we define a random variable Y whichtakes on the values H and T, each with probability 1/2. We can then define an indicatorrandom variable XH, associated with the coin coming up heads, which we can express as theevent Y = H. This variable counts the number of heads obtained in this flip, and it is 1 if thecoin comes up heads and 0 otherwise. We writeThe expected number of heads obtained in one flip of the coin is simply the expected value ofour indicator variable XH:E[XH] = E[I{Y = H}]= 1 · Pr{Y = H} + 0 · Pr{Y = T}= 1 · (1/2) + 0 · (1/2)= 1/2.Thus the expected number of heads obtained by one flip of a fair coin is 1/2.
As the followinglemma shows, the expected value of an indicator random variable associated with an event Ais equal to the probability that A occurs.Lemma 5.1Given a sample space S and an event A in the sample space S, let XA = I{A}. Then E[XA] =Pr{A}.Proof By the definition of an indicator random variable from equation 1) and the definition ofexpected value, we haveE[XA] = E[I{A}]= 1 · Pr{A} + 0 · Pr{Ā}= Pr{A},where Ā denotes S - A, the complement of A.Although indicator random variables may seem cumbersome for an application such ascounting the expected number of heads on a flip of a single coin, they are useful for analyzingsituations in which we perform repeated random trials.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
