作者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