HIRE-ASSISTANT (n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 for i 1 to n 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 问题1： 什么是”确定性”算法？ 这个算法是“确定”的吗？
RANDOMIZED-HIRE-ASSISTANT(n) randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 fori 1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 问题2： 什么是随机算法？ 一这个算法是“随机”的吗？
HIRE-ASSISTANT(n) best 0 /candidate 0 is a least-qualified dummy candidate 2 for i 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 般情况下， 代价会如何？ 问题3： 这个确定算法有“随机”性吗？ 如果我们分析第六条语句的执行条数， 你能给出这个“随机”的概率模型吗？
一般情况下， 代价会如何？
什么是算法的Average-Case Analysis'? 算法的性能依赖于输入数据的随机性 口“好”数据、“差”数据、“不好不差”数据 ■3 完全可以围绕“算法的性能”定义输入数据集（样本空间)上的随机变量 ■算法的平均开销就是这个随机变量的“平均” 口这个随机变量的“期望” We focus on computing the running time of various algorithms. When the running time of an algorithm is different for different inputs of the same size,we can think of the running time of the algorithm as a random variable on the sample space of inputs,and thus,we can analyze the expected running time of the algorithm.This gives us an understanding different from studying just the worst-case running time for an input of a given size
什么是算法的Average-Case Analysis? ◼ 算法的性能依赖于输入数据的随机性 ❑ “好”数据、“差”数据、“不好不差”数据 ◼ 完全可以围绕“算法的性能”定义输入数据集（样本空间）上的随机变量 ◼ 算法的平均开销就是这个随机变量的“平均” ❑ 这个随机变量的“期望
The Difficulty of Average Case Analysis In order to perform a probabilistic analysis,we must use knowledge of,or make assumptions about,the distribution of the inputs Then we analyze our algorithm,computing an average-case running time,where we take the average over the distribution of the possible inputs.Thus we are,in effect,averaging the running time over all possible inputs.When reporting such a running time,we will refer to it as the average-case running time. 输入数据的分布特性失败，必假设定导致平均运行时间分析的失败
The Difficulty of Average Case Analysis 输入数据的分布特性失败，必假设定导致平均运行时间分析的失败