[問題] 有一定機率會對的演算法
看板Prob_Solve (計算數學 Problem Solving)作者s213895 (鬼才)時間17年前 (2007/12/06 12:45)推噓4(4推 0噓 2→)留言6則, 4人參與討論串1/1
我記得曾經耳聞一種演算法
似乎叫普羅旺斯演算法
(但是不確定)
這種演算法當時的範例是
假設有n個數字
那麼我從中隨機選取一個存入big
接下來
{
我再選一個數字
把此數字跟big比較
如比big大 就取代
}
從覆T次
那麼
[
最後big數字將至少比數列的其中一半的數都還大
也就是 至少比(n/2)個數字大
]
以上命題正確的機率為
2^t
我想請教一下 這個演算法是否就叫做普羅旺斯
因為我剛剛查不到這個名字
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.67.113
推
12/06 13:09, , 1F
12/06 13:09, 1F
→
12/06 13:11, , 2F
12/06 13:11, 2F
推
12/06 14:56, , 3F
12/06 14:56, 3F
→
12/06 16:45, , 4F
12/06 16:45, 4F
推
12/06 16:58, , 5F
12/06 16:58, 5F
推
02/15 16:54, , 6F
02/15 16:54, 6F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
