1、隨機(jī)化算法在OI中的應(yīng)用By Nevermore(WYF)為什么要使用隨機(jī)化算法題目出的太詭異你完全不會(huì)做，輸出隨機(jī)數(shù)騙分?jǐn)?shù)據(jù)范圍太大，正常的算法難以想到或非常難實(shí)現(xiàn)（可持久化月下平衡樹套線段樹orz）NPC問題，但是可以用隨機(jī)化在比較能接受的時(shí)間內(nèi)出解總之，隨機(jī)化算法就是在RP和概率的幫助下讓你簡化代碼提高分?jǐn)?shù)的利器那么隨機(jī)化算法都分哪幾類呢？大概有3類，它們都適用于不同的問題，下面我來簡單介紹一下它們。數(shù)值概率算法通過隨機(jī)選取元素從而求得在數(shù)值上的近似解。比傳統(tǒng)的方法速度快。隨著運(yùn)行時(shí)間的增加，近似解的精度也會(huì)提高在一些無法求出精確解或按照解得質(zhì)量給分的題目中，這種方法可以取得不錯(cuò)的效果。

2、常見的數(shù)值概率算法應(yīng)用是在計(jì)算幾何中求面積時(shí)“隨機(jī)撒點(diǎn)”。尤其是在4維空間或以上求體積等傳統(tǒng)方法不好求解的問題中幾乎為最適合的做法Monte Carlo算法這種算法的特點(diǎn)是它總能在確定的時(shí)間內(nèi)出解，然而有一定概率得到錯(cuò)誤的答案，但是通常出錯(cuò)概率很小，我們可以通過多次運(yùn)行來得到可以接受的正確率（比如99.999999999%）常見的Monte Carlo算法有Miller-Rabin素?cái)?shù)測試法，我們在后面會(huì)詳細(xì)介紹此算法Las Vegas算法這種算法總是能返回正確的結(jié)果，然而運(yùn)行時(shí)間卻不確定。通常我們在一些平均時(shí)間復(fù)雜度優(yōu)秀，但是最壞情況下時(shí)間復(fù)雜度很差的算法中，引入隨機(jī)函數(shù)，嘗試減少最壞情況出

3、現(xiàn)次數(shù)，它可以在期望意義下達(dá)到優(yōu)秀的時(shí)間復(fù)雜度常見的Las Vegas 算法有加入隨機(jī)化的快速排序算法快速檢測質(zhì)數(shù)該算法基于以下事實(shí)對于質(zhì)數(shù)p和任意整數(shù)a，有ap a(mod p) 。反過來，滿足ap a(mod p)，p也幾乎一定是質(zhì)數(shù)。每次隨機(jī)取一個(gè)質(zhì)數(shù)p，要檢測的數(shù)a是否滿足上述式子，并多次重復(fù)這個(gè)過程。只要有一次不滿足上式，則這個(gè)數(shù)就不是質(zhì)數(shù)每次運(yùn)行的正確率是3/4，所以稍微多運(yùn)行幾次基本上是不會(huì)出問題的。最小外接圓張角法（不是三國殺里那個(gè)張角）隨機(jī)增量法首先我們有下面的一個(gè)定理(1) 若在原來的點(diǎn)集上新加入一個(gè)點(diǎn)，這個(gè)點(diǎn)在之前的最小外接圓里或邊上，這最小外接圓不變(2)反之，這個(gè)點(diǎn)必定落在新的最小外接圓的邊上隨機(jī)增量法隨機(jī)增量法首先先提一下如何生成一個(gè)完全隨機(jī)的序列假設(shè)你要生成1n的隨機(jī)排列你先令 ai=i (i=1n)然后for(i=2;i=9時(shí)，經(jīng)過數(shù)學(xué)分析，這個(gè)算法的期望運(yùn)行次數(shù)10，而n9時(shí)暴力就可以了這題就這么解決了總結(jié)通過對上述算法的簡要介紹以及對一些例題的分析，可以發(fā)現(xiàn)，隨機(jī)化算法本身的適用范圍很廣，因此不存在什么通用的處理方法。隨機(jī)化算法的優(yōu)勢也是顯而易見的：寫起代碼來簡單，爽可以避免被手工數(shù)據(jù)坑可以用來騙分不過還是有劣勢的，比如分析復(fù)雜，不一定所有問題都適合隨機(jī)等等謝謝觀看參考文獻(xiàn)：2008年國家集訓(xùn)隊(duì)論文感受隨機(jī)的美淺談