作者s213895 (鬼才)
看板Prob_Solve
標題[問題] 有一定機率會對的演算法
時間Thu Dec 6 12:45:08 2007
我記得曾經耳聞一種演算法
似乎叫普羅旺斯演算法
(但是不確定)
這種演算法當時的範例是
假設有n個數字
那麼我從中隨機選取一個存入big
接下來
{
我再選一個數字
把此數字跟big比較
如比big大 就取代
}
從覆T次
那麼
[
最後big數字將至少比數列的其中一半的數都還大
也就是 至少比(n/2)個數字大
]
以上命題正確的機率為
2^t
我想請教一下 這個演算法是否就叫做普羅旺斯
因為我剛剛查不到這個名字
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.67.113
1F：推 ledia:random sample 是蒙地卡羅吧 (Monte Carlo Method) 12/06 13:09
2F：→ ledia:而且應該是 "不正確的機率是 2^T" 12/06 13:11
3F：推 LPH66:2^-T吧? 12/06 14:56
4F：→ ledia:哈 XD 頭暈了 Orz 12/06 16:45
5F：推 s213895:@@ 原來如此 感謝 12/06 16:58
6F：推 jack60133:還有另一種叫拉斯維加斯法，效率上來說就非常地極端 02/15 16:54