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