算法高级教程2.1Introductiontorandomizedalgorithm.pptVIP

* Interviewing has a low cost, say ci, whereas hiring is expensive, costing ch. Let m be the number of people hired. Then the total cost associated with this algorithm is O(nci + mch). Worst-case /Best-case analysis Probabilistic analysis The use of probability in the analysis of problems. Make assumptions about, the distribution of the inputs. * Analysis of the hiring problem let Xi be the indicator random variable associated with the event in which the ith candidate is hired. Thus E[Xi] = Pr {candidate i is hired}=1/i. * Now we can compute E[X]: * Lemma Assuming that the candidates are presented in a random order, algorithm HireAssistant(n) has a total hiring cost of O(chln n). * Randomized hire algorithms RandomizedHireAssistant(n) 1 randomly permute the list of candidates 2 best ← 0 //candidate 0 is a least-qualified dummy candidate 3 for i ← 1 to n do 4 interview candidate i 5 if candidate i is better than candidate best then 6 best ← i 7 hire candidate i * Lemma The expected hiring cost of the procedure RandomizedHireAssistant(n) is O(chln n). * Applications Random algorithms are useful when dealing with the following problem spaces: 1) The adversary conditions that cause deterministic algorithms to perform poorly can be thwarted using random methods to reduce or eliminate their negative affect. 2) If a search space contains a large number of acceptable solutions, a random sample from the population can be used to efficiently find one of them. 3) Random sampling also helps to obtain a solution from a subset of a population to approximately model the entire population. 4) Deadlock and symmetry problems show that randomness is helpful to load balance resources and avoid or break deadlock conditions. * 5) Environments where variety and uncertainty are necessary to provide training use randomness to approximate and simulate real-world effects.