秒懂算法 | 蒙特卡罗算法

主元素问题的蒙特卡罗算法分析、设计与Python实战。

蒙特卡罗算法的基本思想：设p是一个实数，且0.5<p<1。若蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该算法是p正确的；对于同一实例，蒙特卡罗算法不会给出两个不同的正确解，就称该算法是一致的； 而对于一个一致的p正确的蒙特卡罗算法，要想提高获得正确解的概率，只需执行该算法若干次，从中选择出现频率最高的解即可。

在一般情况下，如果设蒙特卡罗算法是一致的p正确的。那么至少调用多少次蒙特卡罗算法，可以使得蒙特卡罗算法得到正确解的概率不低于1-ε(0<ε≤1-p)？

假设至少调用x次，则p+(1-p)p+(1-p)2p+…+(1-p)x-1p≥1-ε，即1-(1-p)x≥1-ε，因为

，所以x≥log1-pε，故。由此可见，无论ε的取值多么小，都可以通过多次调用的方法使得蒙特卡罗算法的优势增强，最终得到一个具有可接受错误概率的算法。

01主元素问题

1●问题分析

设T［1:n］是一个含有n个元素的数组。当|{i