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