Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1800293
  • 博文数量: 438
  • 博客积分: 9799
  • 博客等级: 中将
  • 技术积分: 6092
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-25 17:25
文章分类

全部博文(438)

文章存档

2019年(1)

2013年(8)

2012年(429)

分类: C/C++

2012-04-05 13:11:36

考虑一个雇佣问题:你是一个老板,向猎头公司委托寻找一个秘书职位,猎头每天为你推荐一个应聘者,而你对他进行面试。你的目标是,任 用所有应骋者中资质最好的。但由于秘书职位不能空缺,在每次面试完后,都要立即给面试者结果,所以只要当天的面试者资质比现任秘书好,你就解雇现任的秘 书,而重新雇佣当天的应骋者。下面给出面试n个人的伪代码:


  1. HIRE_ASSISTANT(n) {
  2. 1    best = 0; // candidate 0 is a least-qualified dummy candidate
  3. 2    for i = 1 to n {
  4. 3       interview candidate i;
  5. 4       if candidate i is better than candidate best {
  6. 5          best = i;
  7. 6          hire candidate i;
  8. 7       }
  9. 8    }
  10. }

现在来分析一下面试过程中的花费。这里我们不是分析运行时间,而是花费,但本质是一样的——分析代码执行的代价。设每次进行面试的花费为 c_i,而雇佣一个新秘书的的花费为c_h。c_i的花费比较少,而c_h的花费很高,因为雇佣新的秘书要给猎头一笔佣金,同时解雇现任秘书也需要花费。 假设期间我们雇佣过m个人,则上面算法的总花费为O(c_i*n + c_h*m)。进行面试的花费是固定的,为c_i * n,所以我们关注于雇佣的花费,而雇佣的花费取决于雇佣的次数。在最坏情况下,每天到来的面试者资质都比前一天的好,则每天都要雇佣新的秘书,总花费为O((c_i+c_h)*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)有了显著改善。


随机算法

前面我们的概率分析是基于前提:应骋者到来的顺序是随机分布的。可以看到输入的随机化可以保证我们算法的一个期望值,所以随机算法(先将输入序列随机排列再进行计算)有比较好的平均效率。比如用随机算法重新考虑雇佣问题:


  1. RANDOMIZED_HIRE_ASSISTANT(n) {
  2. 1   randomly permute the list of candidates
  3. 2   HIRE_ASSISTANT(n)
  4. }

它就只多了一步将应骋者序列随机排序的操作,这样可以保证哪怕是猎头刻意造成最坏情况,算法也能有一个很好的期望值。

产生随机排列的一个比较好的方法是原地产生随机序列:


  1. RANDOMIZE_IN_PLACE(A) {
  2. 1   n = A.length;
  3. 2   for i = 1 to n
  4. 3   swap(A[i], A[RANDOM(i, n)]);
  5. }



阅读(3261) | 评论(0) | 转发(5) |
给主人留下些什么吧!~~