雇用问题 雇用策略的伪代码如下: 设应聘者的编号为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的名次，约定较 高的名次对应较有资格的应聘者。 ⚫ 有序序列<rank(1), …, rank(n)> 是 <1, …, n>的一个排列, 例如 <5, 2, 16, 28, 9, … , 11> ⚫ 排名列表构成一个均匀的随机排列(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 ➢ 概率分析：使用关于输入分布的知识或者对其做的假 设，然后分析算法，计算出一个期望的运行时间。 ➢ 实际上是将所有可能输入的运行时间做平均。 ➢ 确定输入的分布时必须非常小心。 • 有些问题，对所有可能的输入集合可以做某种假 定，也可以将概率分析作为一种手段来设计高效 算法，并加深对问题的认识。 • 有些问题可能无法描述一个合理的输入分布，则 不能用概率分析方法