吳師兄領證之前談了多少個女朋友?

前言

這是一篇算法文章。

正文

今天和老婆去領證，有所感想，你的老婆（老公）是你的初戀的機率有多大？

這個還挺難分析的，幸好在《算法導論》一書中找出了參考答案。

在《算法導論》第五章有一個名為「雇傭問題」的案例，它是這樣描述的：

你是一個老闆，向獵頭公司委托尋找一個秘書職位，獵頭每天為你推薦一個應聘者，而你對他進行面試。你的目标是，任用所有應騁者中資質最好的。但由于秘書職位不能空缺，在每次面試完後，都要立即給面試者結果，是以隻要當天的面試者資質比現任秘書好，你就解雇現任的秘書，而重新雇傭當天的應騁者。當然，每次确定雇傭時你都要立馬支付秘書一筆雇傭費用，解雇時費用不返還。

舉個例子，比如有十個人來面試，他們的能力依次為

10 9 8 7 6 5 4 3 2 1

你會發現你找的秘書一屆不如一屆，隻需要支付 1 個機關的費用就行了，這是最省錢的情況。

再舉個例子，還是有十個人來面試，他們的能力依次為

1 2 3 4 5 6 7 8 9 10

由于後者的能力都比前者強，意味着你每次面試完都會解雇之前的秘書，然後馬上雇傭當天的秘書，支出的費用為 10 個機關。

當然，這是最好和最差的情況，用我們國小二年級就學會的階乘知識，出現這種情況的機率為 1/10! 。

是以我們需要計算的是一個期望值，根據《算法導論》給出的答案為 lnN,也就是說，如果有十個人來面試，理論上的支付費用為 2.3 個機關。

上面舉的例子你應該可以輕松的了解，是以《算法導論》馬上增加了難度：

不不不，我們小公司并不需要最好的秘書，時間也比較趕，隻需要比較好的秘書就行啦，我想要省錢。

恩恩，你隻想要支付盡可能少的雇傭費用。

這個情況就和蘇格拉底麥穗的故事一樣。

傳說古希臘哲學大師蘇格拉底的3個弟子曾求教老師，怎樣才能找到理想的伴侶。于是蘇格拉底帶領弟子們來到一片麥田，讓他們每人在麥田中選摘一支最大的麥穗——不能走回頭路，且隻能摘一支。

都是隻給你一次選擇的機會，你需要怎麼樣把握？

答案是先觀察前面的 K 個秘書，記錄下最好秘書的序号，假設為 A，然後繼續面試接下來的秘書們，如果後面出現了比 A 更好的秘書，假設為 B，則雇傭 B，停止面試；如果後面的秘書都不如 A，則雇傭 A，停止面試。

K 是多少呢？

《算法導論》經過一系列的數學推導，得出的數值為 n/e。其中 e 為自然對數。

如果參加面試的秘書數量為 100， K = 100 / 2.7 = 37 ，也就是說你需要走馬觀花的面試這 37 個人，先都委婉的拒絕掉，在後面的面試者裡面如果有比 37 人中最好的那個還要好，馬上發 offer，如果剩下的 63 人都是渣渣，好馬吃回頭草，雇傭 37 人中的優秀者。

将這個理論簡單粗暴的應用到戀愛婚姻上，挺變态的，做個渣男，前幾次隻戀愛不結婚，後面遇到比前面更好的馬上結婚，這樣遇到最合适的人機率最大。

這個結論從反面證明了，從初戀走到結婚的機率有多低，如果你的結婚對象是你的初戀，真的很不容易呀。

那吳師兄領證之前談了多少個女朋友嘞，我們都是彼此的初戀。

參考閱讀：

https://www.zhihu.com/question/332614001/answer/735606441

https://zhuanlan.zhihu.com/p/79865519

https://zhuanlan.zhihu.com/p/70498214

你似乎也發現，「五分鐘學算法」這幾天都是原創，是的，2021 年開始，程式員吳師兄會每天更新一篇原創文章，包括但不限于算法、資料結構、程式設計、程式人生等内容，如果哪天覺得寫得内容不錯，煩請點個贊；如果哪天覺得内容不喜歡，可以隔幾天再來看；如果哪天沒有更新原創，會發個比較可觀的紅包。