算法导论（五）－－概率分析和随机算法

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

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

现在来分析一下面试过程中的花费。这里我们不是分析运行时间，而是花费，但本质是一样的——分析代码执行的代价。设每次进行面试的花费为 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)有了显著改善。

随机算法

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

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

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

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

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