雇佣问题

假设您需要聘请新的办公室助理。 您以前的招聘尝试都没有成功，您承诺每当面试完一位应试者后，如果他的能力比现任助理强，你就解雇当前助理并雇佣该人。你愿意支付解雇和雇佣的费用。

HireAssistant(n)
1 best ← 0
2 for i ← 1 to n do
3 interview candidate i
4 if candidate i is better than candidate best then
5 best ← i
6 hire candidate i.

面试费用c i ， 雇佣费用较高，为c h .。假设雇佣m个人。那么该算法对应的总花费为O(nc i + mc h )。
最差情况
应试者以能力递增的顺序来面试。
最好情况
第一个面试者就是能力最强者。
应试者并不总是以你想要的顺序来应聘。

使用概率方法进行算法分析。
对输入案例服从的概率进行先验性的估计。
使用概率方法需要假设或者提前知晓实例所服从的概率分布，然后求解运行时间的期望。这样我们就得到了一个平均情况下的程序运行时间复杂度。
 决定先验分布需要十分小心。
对于雇佣问题，我们假设应聘者以随机的顺序来应聘。假设我们能够对比两个应聘者的能力高低，那么就能够确定是否雇佣该应聘者。

雇佣问题分析

候选人被雇佣的概率为1/i
雇佣费用c h
雇佣的平均费用为 

当雇佣者以随即顺序来应聘时，  HireAssistant(n)算法总雇佣花费为 O(c h ln n)。