《算法之道》7.6  梦幻情人的概率

我们的情人寻找算法LOVER-FINDER能够让我们每次见到更优秀的异性时立即见异思迁，大大过了一把”良禽择木而栖，好男（女）择女（男）而爱”的瘾。而且更为重要的是，这样一种奢华的恋爱算法居然成本低廉，仅仅是对数级的O(c*ln n)！

一切似乎完美得不能再完美。

但仔细一想，发现这个算法还是有问题。虽然对数级成本在数量级上较低，但这毕竟是多次谈恋爱。而谈多次恋爱的成本毕竟是不少人在精神上、时间上和经济上负担不起的。如果你恰恰又是一个清教徒，则谈多次恋爱还有可能违背你的信仰原则。因此，你决定只能谈一次恋爱！

虽然你是清教徒，或者没有精神和精力去谈多次恋爱，但找到最好的伴侣却是人人都向往的！因此，一个自然的问题是：如果只谈一次恋爱，是否仍能找到称心如意的恋人呢？

那就得看你有没有这个本事啦！不过，这里的本事指的不是忽悠异性的本事，而是算法设计与分析的本事！

显而易见，既然只能谈一次恋爱，但又必须找到最称心如意的梦幻情人，我们便不得不在查看多个候选人的情况下选择一个人作为恋人。为帮助你达到此目标，婚姻介绍所允许你对候选人进行面谈（是见面，或者说相亲，不是真正的谈恋爱）。每次面谈完你必须马上决定是否与该候选人确定恋爱关系。如果决定谈下去，婚姻介绍所即完成使命，将不再提供任何候选人。而如果你不喜欢当前的候选人，则可要求婚姻介绍所换一个人。当然，婚姻介绍所最多提供n个候选人。

面谈虽然不如真正谈恋爱那么伤感情和花费金钱，但也是花费时间和精力的。由于时间和精力有限，你希望将面谈的人数限制在一个较小的范围。因此，你决定先面试k个人，并通通予以拒绝，然后在后面面试中出现的第1个超出前面这k个人的人就是你的恋人。如果后面再无比前面k个人都好的人，则第n个人就是你的恋人，即最坏情况下，你需要面试所有n个候选人。因此，我们新的更加节省费用的情人寻找算法（OPT-LOVE-FINDER(n)）如下：

1. 选择一个k<n。
2. 面试婚姻介绍所介绍的前k个候选人，并予以拒绝。
3. 后面出现的第1个超出前面这k个候选人的人就是恋人。
4. 如果后面不出现超出前面k个人的人，则第n个人就是你的恋人。

这里我们要问的问题就是，应该如何确定k的取值，以使得你的恋人是所有n个候选人里面最好的概率最大！并且计算出这个概率！

对于很多人来说，这个问题乍看之下似乎无从下手。

但仔细分析题意可以看出（也许不容易看出），解答这个问题的步骤应该是先假设我们已经找到了某个k，然后计算在该选定k的取值下，我们获得最佳候选人的概率是多少。然后再根据计算出的概率表达式求极大值即可算出这个k的取值。

现在假定我们已确定了 k 值的大小。很显然，在OPT-LOVE-FINDER 算法的策略下，我们找到梦幻情人（最佳情人）的唯一可能是最佳人选出现在后面的n – k个人当中。如果最佳候选人出现的位置是i，则其前面i – 1个人里面的最优秀的人必须出现在前k个人里面；否则，该最优候选人将成为你的恋人，而不是整个n个候选人里面最好的人！

设E(i) 为候选人i是所有n个人里面最佳候选人的事件，E(k, i) 代表前i个人里面的最佳候选人出现在前k个人里面的事件，E 代表你的恋人是整个n个人里面最佳候选人的事件。

根据上述分析，我们有：

Pr[E]=Pr[E(k+1)E(k,k)]+Pr[E(k+2)E(k,k+1)]+...+Pr[E(n)E(k,n−1)]=∑i=k+1nPr{E(i)E(k,i−1)}

这里，Pr[E(k + 1)E(k, k)]代表的是第k + 1号候选人是最佳人选，并且前k个人里面的局部最佳人选出现在前k个人里的事件发生的概率；Pr[E(k + 2)E(k, k + 1)]代表的是第k + 2号候选人是最佳人选，并且前k + 1个人里面的局部最佳人选出现在前k个人里的事件发生的概率；Pr[E(n)E(k, n – 1)] 代表的是第n号候选人是最佳人选，并且前n – 1个人里面的局部最佳人选出现在前k个人里的事件发生的概率。

由于任何一个候选人是全局最佳人选的概率均等（如果不是这样，我们可以通过随机化手段使得该条件满足），我们有：Pr{E(i)} = 1/n, 且 Pr{E(k, i)} = k/i。因此，

Pr{E}=∑i=k+1nPr{E(i)E(k,i−1)}=∑i=k+1nPr{E(i)}Pr{E(k,i−1)}=∑i=k+1n1n⋅ki−1=kn∑i=kn−11i=kn(∑i=1n−11i−∑i=1k−11i)≈kn(ln(n−1)−ln(k−1))=kn(lnn−1k−1)≈knlnnk

这样，我们就获得在k值给定的情况下，获得最佳人选的概率约为 knlnnk 。对此表达式求取极大值，我们得到 Pr{E} 在 k=ne 的时候获得最大值，并且这个最大值为 1e 。

我们的算法描述如下：

1. 对所有的候选人进行随机排列。
2. 面试前n/e个候选人，并予以拒绝。
3. 后面出现的第1个超出前面这n/e个候选人的人就是恋人。
4. 如果后面不出现超出前面n/e个人的人，则第n个人就是你的恋人。

根据上面的分析，新的情人寻找算法寻找到梦幻情人的概率为1/e，即约36%。但该算法的恋爱成本为常数，即c。而面谈的成本为 ne∗ci ，只有第1个情人寻找算法的约1/3。

阿连在课上提到的算法如下：（和上面提到的概率分析有差异）