參考資料：
概率分析和隨機算法
雇傭問題
在講述概率分析和隨機算法之前，需要先簡單介紹一下，概率論的基礎(chǔ)知識
基礎(chǔ)知識
伯努利試驗：在相同條件下，重復地進行n次相互獨立的實驗 。
有兩種可能的結(jié)果，成功概率：p、失敗概率：q=1-p。
例如：進行n次拋硬幣的實驗。
幾何分布：在n次伯努利試驗中，試驗k次才得到第一次成功的機率。（是離散型概率分布）
例如：進行n次拋硬幣,試驗k次才得到第一次正面的概率。
幾何分布的概率與期望分別是：
幾何分布的概率與期望
二項分布：重復n次獨立的伯努利試驗。在每次試驗中只有兩種可能的結(jié)果，而且兩種結(jié)果發(fā)生與否互相對立，并且相互獨立，與其它各次試驗結(jié)果無關(guān)，事件發(fā)生與否的概率在每一次獨立試驗中都保持不變，則這一系列試驗總稱為n重伯努利實驗。
例如：進行完n次拋硬幣之后,正面出現(xiàn)的次數(shù)
二項分布的概率與期望：
二項分布的概率與期望
0-1分布：就是試驗次數(shù)為1的二項分布
0-1分布的期望：
0-1分布的期望
當然還有一個很重要的調(diào)和級數(shù)：
調(diào)和級數(shù)
概率分析
我們先從一個簡單的問題開始，來介紹概率分析：
首先介紹雇傭問題：假設(shè)你要雇傭一個新的辦公室助理，雇傭代理每天想你推薦一個應(yīng)聘者（連續(xù)推薦n個），你面試這個人，如果這個應(yīng)聘者比目前的辦公室助理更優(yōu)秀，你就會辭掉當前的辦公室助理，然后聘用這個新的。面試一個人需付給雇傭代理一筆費用，聘用辦公助理也需要費用。
也就是只要面試了（不管最后有沒有聘用），就要花費a，如果聘用了，就要再花費b。
雇傭問題
例如，現(xiàn)在有一個人，參加了面試并且最后被聘用了，就要花費a+b的費用。
雇傭問題
所以總的花費就是an+bm，其中n是面試的總?cè)藬?shù)，m是雇傭的次數(shù)，我們最后只雇傭最優(yōu)秀的人，所以只要比前一個雇傭的人優(yōu)秀，那么就開除前一個人，雇傭當前的人。
雇傭花費
所以會有兩種情況出現(xiàn)：
最好情況：面試n次但只雇傭一次(即第一個人就是最優(yōu)秀的人)
那么雇傭費用為：an+b1
最壞情況：面試n次,應(yīng)聘者質(zhì)量按出現(xiàn)的次序嚴格遞增. 面試n次,雇傭n次
那么雇傭費用為：an+bn
但是應(yīng)聘者并非總以質(zhì)量遞增遞減次序出現(xiàn),因此,平均情況下,會雇用多少次？為了解決這個問題，我們就需要進行概率分析了。為了進行概率分析就必須假設(shè)輸入分布。
在雇用問題中
假設(shè)應(yīng)聘者以隨機順序出現(xiàn).即第i應(yīng)聘者都等可能的被雇用。假設(shè)任意兩個應(yīng)聘者間可以比較,可以確定哪一個更有資格。此時，計算平均情況下的雇用費用，即計算雇用一個新的辦公助理的期望。
用X表示雇用新辦公助理的次數(shù),則：
期望
其中Pr{X = x}表示在整個過程中，雇傭了x次的概率，這個計算起來會很麻煩。
所以我們可以換一種思路，將其分解成多個0-1分布來分析：
0-1分布
我們將Xi看做0-1分布，即i被雇傭則為1，不被雇傭則為0。根據(jù)前面所說0-1分布的期望，就是1的概率，在這里也就是應(yīng)聘者i被雇傭的概率。i被雇傭說明他是前i個人里面最優(yōu)秀的那一個，那第i個人是前i個人里最優(yōu)秀的概率是多少呢？顯然是1/i，也就是應(yīng)聘者i被雇傭的概率是1/i。那么我們可以得出Xi的期望E[Xi]=1/i。
那么X也就是所有應(yīng)聘者組成的分布的期望E(X)，根據(jù)調(diào)和級數(shù)，可以計算出結(jié)果，如上圖所示。
所以可以得出在平均情況下的費用：
平均情況費用
從上面雇傭問題中，我想我們已經(jīng)了解到了概率分析
概率分析定義：用概率論方法對不確定性問題進行定量研究，為決策提供定量的依據(jù)。
例如：
概率分析
這個算法是隨著輸入的變化而變化的，對于某個特定的輸入，它總是會產(chǎn)生固定的雇傭次數(shù) — 確定型算法
隨機算法
概率分析是在，輸入已經(jīng)確定的基礎(chǔ)上進行的分析，但是在大多數(shù)情況下,輸入的分布信息無法得知,只能采用隨機算法。
隨機算法
如圖所示，將輸入的序列隨機打亂，可以消除或者減少最壞情況的發(fā)生。
在這里重要的就是RANDOM過程，共有兩種打亂方法，分別是隨機排列數(shù)組和原址排列數(shù)組。
隨機排列數(shù)組
隨機排列數(shù)組
會給原數(shù)組中的每一個元素，生成一個優(yōu)先級數(shù)據(jù)，當然生成的數(shù)字大小范圍是1到結(jié)點個數(shù)的3次方。
最后根據(jù)優(yōu)先級排序，得到結(jié)果。
原址排列數(shù)組
原址排列數(shù)組
這種方法就是將第一個數(shù)與后面隨機選擇的數(shù)進行交換。
原址排列數(shù)組
例如將第一個數(shù)0和后面的數(shù)字8進行交換
原址排列數(shù)組
這里將數(shù)字2和數(shù)字5進行交換。就是這樣進行，這種方法比上一種要好。
概率分析和隨機算法的區(qū)別
概率分析和隨機算法
概率分析：對于某個特定的輸入，它總是會產(chǎn)生固定的結(jié)果。
隨機算法：隨機算法的隨機發(fā)生在算法上，而不是發(fā)生在輸入分布上 .對輸入進行隨機再排列。
最后的小結(jié)：
小結(jié)
