Average case Analysis of an Algorithm 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
Average case Analysis of an Algorithm
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 问题4： 在hiring problem.算法中假设 应聘者随机到达”意味着什么？
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 问题5： 在hiring problem算法中分析算 法所需要的随机变量是什么？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： ·Hiring?操作执行次数：X; E[X]=∑xPr{X=x x=1 ·事件“第个候选人被雇用”的indicator::X; X=X1+X2+…+Xn
Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X ； • 事件“第i个候选人被雇用”的indicator：Xi ;
Indicator Random variable if A occurs, if A does not occur Indicator random variables provide a convenient method for onverting between probabilities and expectations. 问题6： 这句话是什么意思？
Indicator Random Variable