中国科学技术大学：《算法基础》课程教学资源（PPT课件讲稿）第五讲 概率分析与随机算法

第五讲概率分析与随机算法 内容提要: 口雇用问题 口指示器随机变量 口随机算法 口在线雇用问题 2021/2/8

2021/2/8 2 第五讲 概率分析与随机算法 内容提要：  雇用问题  指示器随机变量  随机算法  在线雇用问题

口算法运行肘间与输入规模和输入分布有关,如插入排序: INSERTION-SORT(A) times for(i=2; i0&&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 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: 该方案的费用是多少？ 雇用问题

雇用问题 雇用策略的伪代码如下: 设应聘者的编号为1到n。 假设在面试完应聘者/,可以决定应聘者退是否是你见过的最 适当人选。 为了初始化,建立一个虚拟的应聘者,编号为0,他比所有其他 的应聘者都差。 HIRE-ASSISTANT(n) cost times best +0/ candidate 0 is a least-qualified dummy candidate fori←1ton do interview candidate i f candidate i is better than candidate best then best←i hire candidate i h 费用:n个应聘者中雇用了m个,则该算法的总费用是 o(nc+mcn) 7

7 雇用策略的伪代码如下: ⚫ 设应聘者的编号为1到n。 ⚫ 假设在面试完应聘者i后，可以决定应聘者i是否是你见过的最 适当人选。 ⚫ 为了初始化，建立一个虚拟的应聘者，编号为0，他比所有其他 的应聘者都差。 HIRE-ASSISTANT(n) cost times best ← 0 // candidate 0 is a least-qualified dummy candidate for i ← 1 to n do interview candidate i ci n if candidate i is better than candidate best then best ← i hire candidate i ch m 费用: n 个应聘者中雇用了m个,则该算法的总费用是 O(nci+mch ) 雇用问题

5.1.1 Worst-case analysis HIRE-ASSISTANT(n) cost times best e0// candidate 0 is a least-qualified dummy candidate fori←ton do interview candidate i if candidate i is better than candidate best then best←i hire candidate i 费用:n个应聘者中雇用了m个,则该算法的总费用是O(nc,+mc) 不管雇用多少人,始终要面试n个人,故面试费用总是nc, 我们只专注于分析雇用的费用:m,c>>C1, mC在算法的每次执行中都会改变:与面试应聘者的顺序有关。 最坏情况分析 ◆雇用了n个面试的应聘者.Omc+mcb)=O(nch)?When? ●当应聘者的资质逐渐递增时

8 费用: n 个应聘者中雇用了m个,则该算法的总费用是 。 ⚫ 不管雇用多少人，始终要面试n个人，故面试费用总是n ， ⚫ 我们只专注于分析雇用的费用: , ch >> ci , ⚫ mch 在算法的每次执行中都会改变：与面试应聘者的顺序有关。 最坏情况分析 ◆ 雇用了n个面试的应聘者. O(nci+mch )=O(nch )? When? ◆ 当应聘者的资质逐渐递增时。 HIRE-ASSISTANT(n) cost times best ← 0 // candidate 0 is a least-qualified dummy candidate for i ← 1 to n do interview candidate i ci n if candidate i is better than candidate best then best ← i hire candidate i ch m 5.1.1 Worst-case analysis i c i c mch ( ) O nci + mck

5.1.2 Probabilistic analysis HIRE-ASSISTANT(n) cost times best t0// candidate 0 is a least-qualified dummy candidate fori←1ton do interview candidate i if candidate i is better than candidate best then best←i hire candidate i 假设应聘者的资质序列是任意的: 用1到n将应聘者排列名次,用rnk(表示应聘者名次,约定较 高的名次对应较有资格的应聘者。 、1…,mn(D)34”的一个排列例如<5, 有序序列<rank() 2,16,28,9, 排名列表构成一个均匀的随机排列( uniform random permutation): 在n!种排列中,每种排列以相等的概率出现

9 5.1.2 Propbabilistic analysis 假设应聘者的资质序列是任意的: ⚫ 用1到n将应聘者排列名次，用rank(i)表示应聘者i的名次，约定较 高的名次对应较有资格的应聘者。 ⚫ 有序序列 是 的一个排列, 例如 ⚫ 排名列表构成一个均匀的随机排列(uniform random permutation ): 在 n!种排列中，每种排列以相等的概率出现。 HIRE-ASSISTANT(n) cost times best ← 0 // candidate 0 is a least-qualified dummy candidate for i ← 1 to n do interview candidate i ci n if candidate i is better than candidate best then best ← i hire candidate i ch m

5.1.2 Probabilistic analysis 概率分析:在问题的分析中应用概率技术。 使用概率分析来分析一个算法的运行时间,或其他 的量。 概率分析的本质:需已知或假定输入的概率分布 依据概率分布来求期望,期望值即是平均雇用的人数 52节介绍了雇佣问题的概率分析

10 5.1.2 Propbabilistic analysis 概率分析的本质：需已知或假定输入的概率分布 ⚫ 依据概率分布来求期望，期望值即是平均雇用的人数 ⚫ 5.2节介绍了雇佣问题的概率分析。 • 概率分析：在问题的分析中应用概率技术。 • 使用概率分析来分析一个算法的运行时间，或其他 的量

5.1.2 Probabilistic analysis 概率分析:使用关于输入分布的知识或者对其做的假 设,然后分析算法,计算出一个期望的运行时间。 实际上是将所有可能输入的运行时间做平均。 确定输入的分布时必须非常小心。 有些问题,对所有可能的输入集合可以做某种假 定,也可以将概率分析作为一种手段来设计高效 算法,并加深对问题的认识。 有些问题可能无法描述一个合理的输入分布,则 不能用概率分析方法

5.1.2 Propbabilistic analysis ➢ 概率分析：使用关于输入分布的知识或者对其做的假 设，然后分析算法，计算出一个期望的运行时间。 ➢ 实际上是将所有可能输入的运行时间做平均。 ➢ 确定输入的分布时必须非常小心。 • 有些问题，对所有可能的输入集合可以做某种假 定，也可以将概率分析作为一种手段来设计高效 算法，并加深对问题的认识。 • 有些问题可能无法描述一个合理的输入分布，则 不能用概率分析方法