HIRE-ASSISTANT(n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 fori 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 问题5： 在niring problem算法中分析算 法所需要的随机变量是什么？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： 。Hiring操作执行次数：X E[X]=∑xPr{X=x t= 这个公式的计算，难在哪里？ 观察到这个问题其实是在分析（甚至是统计）重 复独立试验，能否简化？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X 这个公式的计算，难在哪里？ 观察到这个问题其实是在分析（甚至是统计）重 复独立试验，能否简化？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： 。·Hiring操作执行次数：X; 0 事件“第个候选人被雇用”的indicator::X,; X=X1+X2+…+Xm E[X] (by equation(5.2)) ∑EXI (by linearity of expectation) i= n (by equation(5.3)) E[x]=1/i i= Inn +0(1)(by equation (A.7)). 为什么？
Hiring-Assistant算法的平均情况分析 涉及的随机变量： • Hiring操作执行次数：X ； • 事件“第i个候选人被雇用”的indicator：Xi ; 为什么？
基于概率的算法分析与随机算法 ·输入数据的概率模型 outcomes,sample space,probability probability variant 口通过分布、期望来进行平均时间开销分析 ·难以给出概率模型时： 口“制造”一个随机分布，进而利用这个随机分布进行概率分析
基于概率的算法分析与随机算法 ◼ 输入数据的概率模型 ❑ outcomes，sample space，probability ❑ probability variant ❑ 通过分布、期望来进行平均时间开销分析 ◼ 难以给出概率模型时： ❑ “制造”一个随机分布，进而利用这个随机分布进行概率分析
随机算法 RANDOMIZED-HIRE-ASSISTANT(n) randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 for i 1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 相当于用抛硬币或 算法的执行不再依赖 者掷色子的方式决 于输入数据，关键取 定下一步该干什么！决于一个“随机数” 这个随机现像，我们可以清楚认识它的班率模型
随机算法 相当于用抛硬币或 者掷色子的方式决 定下一步该干什么！ 算法的执行不再依赖 于输入数据，关键取 决于一个“随机数” 这个随机现象，我们可以清楚认识它的概率模型