參考資料：
概率分析和隨機(jī)算法
雇傭問(wèn)題
在講述概率分析和隨機(jī)算法之前浩姥，需要先簡(jiǎn)單介紹一下鸵贬，概率論的基礎(chǔ)知識(shí)
基礎(chǔ)知識(shí)
伯努利試驗(yàn)：在相同條件下嘀趟，重復(fù)地進(jìn)行n次相互獨(dú)立的實(shí)驗(yàn) 嚷狞。
有兩種可能的結(jié)果，成功概率：p蛔钙、失敗概率：q=1-p锌云。
例如：進(jìn)行n次拋硬幣的實(shí)驗(yàn)荠医。
幾何分布：在n次伯努利試驗(yàn)中吁脱，試驗(yàn)k次才得到第一次成功的機(jī)率。（是離散型概率分布）
例如：進(jìn)行n次拋硬幣,試驗(yàn)k次才得到第一次正面的概率彬向。
幾何分布的概率與期望分別是：
二項(xiàng)分布：重復(fù)n次獨(dú)立的伯努利試驗(yàn)兼贡。在每次試驗(yàn)中只有兩種可能的結(jié)果，而且兩種結(jié)果發(fā)生與否互相對(duì)立娃胆，并且相互獨(dú)立遍希，與其它各次試驗(yàn)結(jié)果無(wú)關(guān)，事件發(fā)生與否的概率在每一次獨(dú)立試驗(yàn)中都保持不變里烦，則這一系列試驗(yàn)總稱為n重伯努利實(shí)驗(yàn)凿蒜。
例如：進(jìn)行完n次拋硬幣之后,正面出現(xiàn)的次數(shù)
二項(xiàng)分布的概率與期望：
0-1分布：就是試驗(yàn)次數(shù)為1的二項(xiàng)分布
0-1分布的期望：
當(dāng)然還有一個(gè)很重要的調(diào)和級(jí)數(shù)：
概率分析
我們先從一個(gè)簡(jiǎn)單的問(wèn)題開(kāi)始，來(lái)介紹概率分析：
首先介紹雇傭問(wèn)題：假設(shè)你要雇傭一個(gè)新的辦公室助理胁黑，雇傭代理每天想你推薦一個(gè)應(yīng)聘者（連續(xù)推薦n個(gè)）废封，你面試這個(gè)人，如果這個(gè)應(yīng)聘者比目前的辦公室助理更優(yōu)秀丧蘸，你就會(huì)辭掉當(dāng)前的辦公室助理漂洋，然后聘用這個(gè)新的。面試一個(gè)人需付給雇傭代理一筆費(fèi)用力喷，聘用辦公助理也需要費(fèi)用刽漂。
也就是只要面試了（不管最后有沒(méi)有聘用），就要花費(fèi)a弟孟，如果聘用了贝咙，就要再花費(fèi)b。
例如拂募，現(xiàn)在有一個(gè)人庭猩，參加了面試并且最后被聘用了，就要花費(fèi)a+b的費(fèi)用没讲。
所以總的花費(fèi)就是an+bm眯娱，其中n是面試的總?cè)藬?shù)，m是雇傭的次數(shù)爬凑，我們最后只雇傭最優(yōu)秀的人徙缴，所以只要比前一個(gè)雇傭的人優(yōu)秀，那么就開(kāi)除前一個(gè)人，雇傭當(dāng)前的人于样。
所以會(huì)有兩種情況出現(xiàn)：
最好情況：面試n次但只雇傭一次(即第一個(gè)人就是最優(yōu)秀的人)
那么雇傭費(fèi)用為：an+b1
最壞情況：面試n次,應(yīng)聘者質(zhì)量按出現(xiàn)的次序嚴(yán)格遞增. 面試n次,雇傭n次
那么雇傭費(fèi)用為：an+bn
但是應(yīng)聘者并非總以質(zhì)量遞增遞減次序出現(xiàn),因此,平均情況下,會(huì)雇用多少次疏叨？為了解決這個(gè)問(wèn)題，我們就需要進(jìn)行概率分析了穿剖。為了進(jìn)行概率分析就必須假設(shè)輸入分布蚤蔓。
在雇用問(wèn)題中
假設(shè)應(yīng)聘者以隨機(jī)順序出現(xiàn).即第i應(yīng)聘者都等可能的被雇用。假設(shè)任意兩個(gè)應(yīng)聘者間可以比較,可以確定哪一個(gè)更有資格糊余。此時(shí)秀又，計(jì)算平均情況下的雇用費(fèi)用，即計(jì)算雇用一個(gè)新的辦公助理的期望贬芥。
用X表示雇用新辦公助理的次數(shù),則：
其中Pr{X = x}表示在整個(gè)過(guò)程中吐辙，雇傭了x次的概率，這個(gè)計(jì)算起來(lái)會(huì)很麻煩蘸劈。
所以我們可以換一種思路昏苏，將其分解成多個(gè)0-1分布來(lái)分析：
我們將Xi看做0-1分布，即i被雇傭則為1威沫，不被雇傭則為0贤惯。根據(jù)前面所說(shuō)0-1分布的期望，就是1的概率棒掠，在這里也就是應(yīng)聘者i被雇傭的概率孵构。i被雇傭說(shuō)明他是前i個(gè)人里面最優(yōu)秀的那一個(gè)，那第i個(gè)人是前i個(gè)人里最優(yōu)秀的概率是多少呢句柠？顯然是1/i浦译，也就是應(yīng)聘者i被雇傭的概率是1/i。那么我們可以得出Xi的期望E[Xi]=1/i溯职。
那么X也就是所有應(yīng)聘者組成的分布的期望E(X)精盅，根據(jù)調(diào)和級(jí)數(shù)，可以計(jì)算出結(jié)果谜酒，如上圖所示叹俏。
所以可以得出在平均情況下的費(fèi)用：
從上面雇傭問(wèn)題中，我想我們已經(jīng)了解到了概率分析
概率分析定義：用概率論方法對(duì)不確定性問(wèn)題進(jìn)行定量研究僻族，為決策提供定量的依據(jù)粘驰。
例如：
這個(gè)算法是隨著輸入的變化而變化的，對(duì)于某個(gè)特定的輸入述么，它總是會(huì)產(chǎn)生固定的雇傭次數(shù) — 確定型算法
隨機(jī)算法
概率分析是在蝌数，輸入已經(jīng)確定的基礎(chǔ)上進(jìn)行的分析，但是在大多數(shù)情況下,輸入的分布信息無(wú)法得知,只能采用隨機(jī)算法度秘。
如圖所示顶伞，將輸入的序列隨機(jī)打亂，可以消除或者減少最壞情況的發(fā)生。
在這里重要的就是RANDOM過(guò)程唆貌，共有兩種打亂方法滑潘，分別是隨機(jī)排列數(shù)組和原址排列數(shù)組。
隨機(jī)排列數(shù)組
會(huì)給原數(shù)組中的每一個(gè)元素锨咙，生成一個(gè)優(yōu)先級(jí)數(shù)據(jù)语卤，當(dāng)然生成的數(shù)字大小范圍是1到結(jié)點(diǎn)個(gè)數(shù)的3次方。
最后根據(jù)優(yōu)先級(jí)排序酪刀，得到結(jié)果粹舵。
原址排列數(shù)組
這種方法就是將第一個(gè)數(shù)與后面隨機(jī)選擇的數(shù)進(jìn)行交換。
例如將第一個(gè)數(shù)0和后面的數(shù)字8進(jìn)行交換
這里將數(shù)字2和數(shù)字5進(jìn)行交換蓖宦。就是這樣進(jìn)行齐婴，這種方法比上一種要好油猫。
概率分析和隨機(jī)算法的區(qū)別
概率分析：對(duì)于某個(gè)特定的輸入稠茂，它總是會(huì)產(chǎn)生固定的結(jié)果。
隨機(jī)算法：隨機(jī)算法的隨機(jī)發(fā)生在算法上情妖，而不是發(fā)生在輸入分布上 .對(duì)輸入進(jìn)行隨機(jī)再排列睬关。
最后的小結(jié)：
