【算法】3 由招聘問題看随機算法

我想看我部落格的還是學生人群偏多吧，本身很快就要去面試了，在這篇部落格的問題中，我們就把自己當作boss過把瘾。

某天，你想雇用一名算法工程師。當然，不可能讓你這個boss親自去到處練習應聘者，而是選擇了中介。雇用中介每天都會給你推薦一個應聘者（ps：還是讓自己輕松點，一天隻應聘一個人哈）。是個地球人都知道，你必須要給中介付一小筆錢。然後如果你雇用了一個應聘者則需要更多的錢，一來你要解雇現有的算法工程師，更重要的是你要付給中介一大筆錢。在這個問題中還有一個關鍵的問題，雖然有些不合情理——隻要遇到更好的算法工程師，你都會把之前的給解雇掉（忽略合同等等哦）。

相信大家一看這個問題就知道重點是什麼了，錢，錢，錢，還是錢。你希望費用是最低的。

那麼解決這個問題的邏輯呢，當然就是：

1）從1到n個應聘者中不斷地面試

2）如果目前應聘者比上一個更好，則雇用目前應聘者并解雇上一個雇用者

問題是如何将實際問題轉換成僞代碼，僞代碼才是最重要的，有了它你便可以将其改成任何語言的描述。

相比大家都看過該系列的前兩篇算法博文呢吧？這一篇和前面兩篇的差別在于問題的角度不同了，以前我們考慮執行時間，現在我們考慮雇用所花的費用。

大家想想這和前面用到的歸并排序有哪些相似點呢？

不管是執行時間，還是花費費用，在算法之中都是由一些操作來執行的，是以終究還是逃離不了算法的分析。

如前所述，假定總共有n個人需要面試，有m個人最終被雇用。面試一個應聘者時需要給中介的費用是小的，設為cs；而在你面試通過了這個應聘者後給中介的費用才是大的，設為cb。

是以這個算法總共要花費的費用為o(csn+cbm)。大家應該有很清晰的了解這個問題吧？為什麼最終由m個人被雇用而不是1個人被雇用呢。原因是這樣的：比如說你現在面試了一個應聘者，你覺得他蠻優秀的，但是在10天你又遇到了一個更加優秀的，于是你便辭退了先前的雇員，聘請了最新看中的應聘者。

是以說，無論如何我們都會面試n個人，總費用csn也是固定的，真正對算法有着深遠（波動）影響的應該是這雇用的m個人。

這個是時候，我們就按情況的不同作具體分析了。

很顯然，如果這些應聘者按優秀程度（僅僅是舉個例子）來遞增順序進行面試，最優秀的最先面試，那麼你在應聘這個方面所花費的價錢就僅僅是cs∗1了。

相反，如果是按照遞減順序進行面試，那優秀的最後面試，那麼這下麻煩可大了，你所花費的價錢就是cs∗n，如果n特别大那就更加糟糕了。

這個例子也許不夠讓大家印象深刻，那就再來一個例子。就比如說學校、公司、電視台等的各種晚會，為了更加吸引觀衆更多的關注當然要最好的節目留在最後了，這也是傳說中的壓軸。如果最後的節目一開始就結束了，後面的節目也許就沒多人人想看了，這個問題就是前面的雇用問題有着相同的思想，當然了，情況是相反的。說到壓軸，也許舉聯考的例子更加合适吧？如果把壓軸題放在一開始，或者随意放置……那豈不是一片混亂？為了考生考慮都統一把壓軸題放到了最後。

如果大家了解了上面的描述，那就相當于了解了最壞情況分析。

在這個算法中，我們顯然不可能每次都去強制控制它的輸入，是以便有了随機算法這麼一說。

所謂的随機算法，就是使用排列的順序随意。選取一個主元，輸入的順序便不重要了。無論所提供的輸入是遞增排序還是遞減排序，亦或是沒有排序，都對算法沒有影響，因為輸入是什麼根本就不重要了。我們都會将其打亂，讓它們随機分布。

既然選擇了這個算法，自然有它的優點：

1）它的運作時間不依賴于輸入序列的順序

2）無需對輸入序列的釋出做任何假設

3）無論是怎樣的輸入都不會引發最差的運作情況

4）而最差的情況卻是由随機數産生器決定的

那麼什麼樣的算法是随機的呢？

其行為不僅由輸入決定，而且也有随機數生成器産生的數值決定，這種算法就是随機的。

話說回來什麼叫做随機數生成器呢？

随機數生成器random，通過調用random(a,b)而傳回a到b之間的整數且每個整數都以等機率出現。

然而許多程式設計環境/語言都會提供一個僞随機數生成器（比如說c#裡面的random），它其實是一個确定性算法，隻不過其結果在統計上看上去是随機的。

在分析随機算法時，和前面的就有差別了。我們開始以運作時間的期望值來衡量，而輸入值也通過随機數來生成。是以随機算法的運作時間也叫做期望運作時間，因為這一切都是不确定的，是以我們隻能期望，期望，期望。

如果一個算法的輸入是機率分布的，那麼就分析其平均情況運作時間；當算法本身對于輸入可以通過随機過程來選擇，那麼就分析其期望運作時間。

我們不是假設輸入的一個分布，而是設定一個釋出。也就是說在這個算法開始前，先随機化它的輸入，讓這些輸入擁有等可能的出現機率。

每次運作這個算法時，執行都依賴于随機選擇，是以執行很和前面的不同。是以變有了前面”無論是怎樣的輸入都不會引發最差的運作情況“的優點。

是以對于前面的僞代碼唯一需要改變的隻是增加”随機化應聘者序列“這一段。

那麼問題來了，僞代碼中的第1行該如何實作呢？還記得鍵值對麼，這是我一開始覺得比較牛叉的概念，後來發現也不過如此。這裡我們就可以用到這個理念。

我們給數組中的每個元素賦一個優先級，優先級和數組中的元素都是數字。以往我們給數組中的元素排序都是直接按元素的大小進行比較、排序的，這裡則跑開了元素本身，通過元素對應的優先級來比較，優先級優先的數即更小，我們也可以将其排在後面。

這裡我們将優先級是範圍設為了1到n2，其實隻是為了擴大它的範圍以不至于優先級重疊，你當然也可以設定為n的三次方，或是4次方。

感謝您的通路，希望對您有所幫助。 歡迎大家關注、收藏以及評論。

為使本文得到斧正和提問，轉載請注明出處：

http://blog.csdn.net/nomasp