第五讲概率分析与随机算法 内容提要: 口雇用问题 口指示器随机变量 口随机算法 口在线雇用问题 2021/2/8
2021/2/8 2 第五讲 概率分析与随机算法 内容提要： 雇用问题 指示器随机变量 随机算法 在线雇用问题
口算法运行肘间与输入规模和输入分布有关,如插入排序: INSERTION-SORT(A) times for(i=2; i<=length A: ++ 2 key=AlI -1 ∥ nsert All into the sorted sequence All1…j10 -1 i=i-I while(i>0&&Ali> key Ai+1=Ai Ali+1=key -1 7(m)=cn+c(n-1)+c(m-1)+c∑1+c∑(1-1)+c∑(1-1)+c(n-1) 2021/2/8
2021/2/8 3 算法运行时间与输入规模和输入分布有关，如插入排序： 1 2 4 5 6 7 8 2 2 2 ( ) ( 1) ( 1) ( 1) ( 1) ( 1) n n n j j j j j j T n c n c n c n c t c t c t c n = = = = + − + − + + − + − + − INSERTION-SORT(A) cost times 1 for( j = 2; j <=length[A]; j++) c1 n 2 { key = A[j] c2 n-1 3 // Insert A[j] into the sorted sequence A[1 .. j-1] 0 n-1 4 i = j-1 c4 n-1 5 while( i > 0 && A[i] > key) c5 6 { A[i+1] = A[i] c6 7 i = i-1 c7 8 } 9 A[i+1] = key c8 n-1 10 }
口对于运算时间与输入数据分布有关的算法,时间复杂度分析一般 有三种:最坏运行时间、最佳运行时间、平均运行时间 口平均运行时间是算法对所有可能情况的期望运行时间,与输入数 据的概率分布有关。 口分析算法的平均运行时间通常需要对输入分布做某种假定 2021/2/8
对于运算时间与输入数据分布有关的算法，时间复杂度分析一般 有三种：最坏运行时间、最佳运行时间、平均运行时间。 平均运行时间是算法对所有可能情况的期望运行时间，与输入数 据的概率分布有关。 分析算法的平均运行时间通常需要对输入分布做某种假定 2021/2/8 4
第五讲概率分析与随机算法 内容提要: 口雇用问题 口指示器随机变量 口随机算法 口在线雇用问题 2021/2/8
2021/2/8 5 第五讲 概率分析与随机算法 内容提要： 雇用问题 指示器随机变量 随机算法 在线雇用问题
雇用问题 情景:一个月内雇用最佳人任办公室助理 猎头公司帮你物色办公助理候选人 每天推荐一名候选人 面试候选人之后决定是否雇用,如果这个应聘者比目前的办公室 助理更有资格,会辞掉目前的办公室助理,聘用这个新的应聘者 面试一个候选人支付猎头公司1K 雇用一名候选人代价是1W(解雇目前办公助理的代价+支付给猎 头公司的中介费用 Goa:该方案的费用是多少?
6 情景 : 一个月内雇用最佳人任办公室助理 ⚫ 猎头公司帮你物色办公助理候选人 ⚫ 每天推荐一名候选人 ⚫ 面试候选人之后决定是否雇用，如果这个应聘者比目前的办公室 助理更有资格，会辞掉目前的办公室助理，聘用这个新的应聘者 ⚫ 面试一个候选人支付猎头公司1K ⚫ 雇用一名候选人代价是1W(解雇目前办公助理的代价+ 支付给猎 头公司的中介费用). Goal: 该方案的费用是多少？ 雇用问题