【问答】算法数据结构里面有没有什么有趣的内容？

原载于：www.zhihu.com/question/33…

有很多。

我记得《算法导论》里就有一些很有意思的例子，惊喜在本文末尾。

第五章有一个「雇佣问题」（有删改）

假设你要招一个前端工程师，发现没有合适的人选。
于是你找了一个猎头。不是猪头，是猎头。
假设猎头每天给你推荐一个应聘者，你会去面试这个人，然后马上决定要不要录用他/她。
假设你每次面试都需要支付给猎头一笔小费用，如果你决定录用一个人则需要支付一大笔费用给猎头的公司。
你可以今天录用一个人，然后第二天反悔录用另一个人，但是这样你就要付两大笔钱。
你一旦发现今天的面试者比之前决定录用的人好，就会改为录用今天的面试者。

前提条件基本是这样，然后就是分析了。

由于有多少人你就要面试多少次，所以小费用这一部分没法节省。

问题的关键就在于如何尽量减少大费用的支出了。

最坏情况分析

最坏的情况就是 n 个应聘者的质量逐天递增，你每次都发现你每天都要花一大笔钱用今天的面试者替换昨天的。这实在是很烧钱。

概率分析

最坏情况是很难出现的，我们应该计算一个平均情况。

假设 n 个应聘者的水平排名是 1 到 n；

假设这些应聘者出现的顺序是随机的；

那么面试官面对的就是一个均匀的随机序列，如果 n 是 3，那么这些应聘者出现的顺序可能是

• 1 2 3
• 1 3 2
• 2 1 3
• 2 3 1
• 3 1 2
• 3 2 1

一共有 n! （n的阶乘）种情况。

然后书中利用一些概率公式得出一个结论：只需要录用

个人（期望值）。

这个结果令人疑惑，因为假设有 10 个人来面试，他们的水平依次是 1 2 3 4 5 6 7 8 9 10，显然我们的录用次数会是 9。

的结果却是 2.3 左右。

然后书中说你只需要把应聘者出现的顺序随机化一下，结果就会接近 2.3 了。

到此，第一个例子就完了。这个例子看起来有些不符合实际，因为每录用一次就付钱那猎头公司实在是太赚了。

所以书后面又有一个变形的题目：

假设现在我们不想要面试完所有人然后找一个最好的，也不希望不停地录用新人换之前录用的人，
怎么着呢？我们希望录用一个接近最好的应聘者，而且只录用一次。
假设每次面试后必须立马告诉录用结果，不能拖几天再决定。
请问，如何通过尽量少的面试次数，录用水平尽量高的应聘者呢？

这个题目就非常接近现实生活中的面试了。

书中的面试策略是这样的：

选择一个正整数 k < n，面试前 k 个应聘者然后拒绝他们，之后的应聘者只要有一个比前 k 个的最高水平高，就录用他/她。

然后书中又一顿骚操作，得出 k 的值：n/e 。

也就是说，如果有 100 名随机出现的应聘者，只需要面试前 37 人，全部拒绝掉，然后只要遇到一个比这 37 人都好的，录用即可。这样录用到最好的应聘者的概率是最高的。

不知道各位是怎么想的，反正我当时觉得这个脑回路真的是很神奇，居然还有这种面试方法。

但当我把这个算法放到另一个领域，就发现了更奇葩的脑回路了。

找老婆/老公

假设你一生中会随机遇到 n 个异性，你跟ta相遇之后就要决定是跟ta交往还是不跟ta交往，不可以劈腿，最终你只能选择一个人结婚而且只能选一次，请问，你该怎么选，才能最大可能地选中最合适你的那个人？

答案跟上面的面试策略很像：先依次跟前 n / e 个异性交往，记下其分数，然后全部分手。之后，只要遇到一个比前面都好的异性，就结婚。这是最优解。（当然你也可以不顾时间、精力和金钱成本跟每个异性都交往看看，但那不是最优解）

这个策略是不是有点——或者说非常——渣。

但是好像就是事实……假设一个男人在求偶期总共会遇到 10 个女人，那么 10 / e 的值就是 3.7。这跟非诚勿扰的统计数据非常吻合！非诚勿扰的男嘉宾基本都会说自己曾经有过 3 到 4 段恋情。原来这里面是有科学依据的呀（大误）。

另一个启发就是，如果你的求偶期已经过了一半了，那么你可能只能遇到 5 个女人，那么你的值就是 5 / e 结果是 1.8。也就是说，你谈一两段恋爱之后就结婚是最好的。

那如果你已经出在求偶期的末尾呢？答案是……只要有人愿意你就跟ta结婚才是最好的，别挑了，越挑结果越差。(剩男剩女注意了，敲黑板）

再假设你是王某聪，求偶期遇到的女人是 200 个，那么，前 74 个都不要选，从第 75 个开始再选。

假设你是个女人，你想嫁给王某聪，你应该尽量出现在 75 个左右，并且尽量让自己的素质高于前面 74 个。这个竞争压力还真的是很大啊。

最后，这个算法还可以用来劝导早恋：最早交往的那些异性，肯定不是跟你走到最后的人。是不是很虐，哈哈。

总结

以上都是脑洞而已。算法是枯燥的，只有学会苦中作乐，才能深入学习算法知识。

共勉。

另外说实话，算法导论中的精髓就是那些骚操作，但也是最难懂的，我一般都是直接跳过看代码。

完。