阅读 401

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

原载于: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 个。这个竞争压力还真的是很大啊。

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

总结

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

共勉。

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

完。

关注下面的标签,发现更多相似文章
评论