分类:
2012-04-07 12:27:29
原文地址:算法导论(五)--概率分析和随机算法 作者:yourtommy
考虑一个雇佣问题:你是一个老板,向猎头公司委托寻找一个秘书职位,猎头每天为你推荐一个应聘者,而你对他进行面试。你的目标是,任 用所有应骋者中资质最好的。但由于秘书职位不能空缺,在每次面试完后,都要立即给面试者结果,所以只要当天的面试者资质比现任秘书好,你就解雇现任的秘 书,而重新雇佣当天的应骋者。下面给出面试n个人的伪代码:
给定一个样本空间S和事件A,那么事件A对应的指示器变量I{A}的定义为:
I{A} = 1 如果A发生的话
or = 0 如果A不发生的话
比如抛一枚均匀硬币,样本空间为S={H, T} (H为正面朝上,T为背面朝上),正反面朝上的概率都分别为1/2,即Pr{H} = Pr{T} = 1/2。我们用指示器随机变量X_H来对应正面朝上的情况,则:
X_H = I{H} = 1 如果H发生,即正面朝上
or = 0 如果T发生,即背面朝上
我们可以计算抛一次硬币时指示器随机变量X_H的期望值:
E[X_H] = E[I{H}] = 1*Pr{H} + 0*pr{T} = 1*1/2 + 0*1/2 = 1/2
不难发现,指示器随机变量的期望值等于对应事件发生的概率。
现在连续抛硬币n次,假设随机变量X_i对应第i次抛硬币时正面朝上的事件:X_i = I{第i次抛硬币的正面朝上}。
我们用随机变量X来对应n次抛硬币中正面朝上的总次数:X = ∑X_i。则正面朝上的期望次数为:
E[X] = E[∑ X_i] = ∑ E[X_i] = ∑1/2 = n/2
现在回到刚才的雇佣问题,我们用指示器随机变量来分析花费:假设X_i对应事件A“第i个应骋者被雇佣”:
X_i = I{A} = 1 如果应骋者i被雇佣
or = 0 如果应骋者i没有被雇佣
事件A的概率为:应骋者是1...i中最好的概率 = 1/i,所以X_i值的期望值也为1/i。用随机变量X表示雇佣的总次数:
X = X_1 + X_2 + ... + X_n
则X的期望值为:
E[X] = E[∑ X_i] = ∑ E[X_i] = ∑ 1/i = ln(n) + O(1) (调合级数的求和)
综上所述,在应骋者以随机的次序出现时,面试n个人后平均雇佣的人数为ln(n) + O(1),而HIRE_ASSISTANCE总的雇佣费用为O(c_h*ln(n))。期望的雇佣费用比最坏情况下的雇佣费用O(c_h*n)有了显著改善。
随机算法
前面我们的概率分析是基于前提:应骋者到来的顺序是随机分布的。可以看到输入的随机化可以保证我们算法的一个期望值,所以随机算法(先将输入序列随机排列再进行计算)有比较好的平均效率。比如用随机算法重新考虑雇佣问题:
产生随机排列的一个比较好的方法是原地产生随机序列: