わたしの部屋

1. 什么是蒙特卡罗算法#

蒙特卡罗算法（Monte Carlo Algorithm）是一类基于随机采样和概率统计的算法。

它的核心思想是：

当一个问题很难直接精确求解时，可以通过大量随机实验，用统计结果去近似真实答案。

简单来说，蒙特卡罗算法的流程是：

1
随机生成样本 → 统计样本结果 → 用样本比例估计整体结果

它不一定每次都能得到完全精确的答案，但随着随机采样次数增加，结果通常会越来越接近真实值。

2. 随机化算法的两种类型#

在计算机科学中，随机化算法通常可以分为两类：蒙特卡罗算法和拉斯维加斯算法。

蒙特卡罗算法的特点是：运行时间通常是确定或有限的，但结果可能存在误差。

例如用随机点估算圆周率 $\pi$，如果规定生成 $1000000$ 个点，那么采样次数是固定的；但估算出的 $\pi$ 只是近似值。通过增加随机采样次数，可以让误差概率不断降低，使结果越来越接近真实值。

拉斯维加斯算法的特点是：运行时间带有随机性，但只要算法结束，得到的结果一定正确。

例如随机化快速排序，随机选择基准值 pivot 会影响划分效果，从而影响运行时间；但排序完成后，结果一定是正确的。

区分

蒙特卡罗算法保证时间可控，算的是精度；拉斯维加斯算法保证答案正确，赌的是时间。

3. 经典例子：估算圆周率 π#

蒙特卡罗算法最经典的入门例子，就是用随机点估算圆周率 $\pi$。

4. 算法步骤#

根据上面的推导，代码只需要做三件事：

1. 在正方形内均匀生成随机点；
2. 统计有多少点落在单位圆内；
3. 用圆内点比例估算 $\pi$：

5. Java 代码实现#

1
import java.util.Random;
2

3
public class MonteCarloPi {
4
    public static double estimatePi(int n) {
5
        if (n <= 0) {
6
            throw new IllegalArgumentException("采样次数必须大于 0");
7
        }
8

9
        Random random = new Random();
10
        long inside = 0;
11

12
        for (int i = 0; i < n; i++) {
13
            // random.nextDouble() 生成 [0, 1) 之间的小数
14
            // 乘以 2 后变成 [0, 2)，再减去 1 后变成 [-1, 1)
15
            double x = random.nextDouble() * 2 - 1;
16
            double y = random.nextDouble() * 2 - 1;
17

18
            // 判断点是否落在单位圆内
19
            if (x * x + y * y <= 1) {
20
                inside++;
21
            }
22
        }
23

24
        return 4.0 * inside / n;
25
    }
26

27
    public static void main(String[] args) {
28
        System.out.println(estimatePi(1000));
29
        System.out.println(estimatePi(10000));
30
        System.out.println(estimatePi(100000));
31
        System.out.println(estimatePi(1000000));
32
    }
33
}

可能的输出：

1
3.108
2
3.1464
3
3.13972
4
3.14188

由于使用了随机数，每次运行的结果可能都不完全一样。但通常来说，采样次数越多，结果越接近真实的 $\pi$。

6. 复杂度分析#

假设采样次数为 $n$。每次采样只需要生成两个随机数并进行一次判断，都是常数时间操作。

• 时间复杂度：$O(n)$，$n$ 为采样次数。
• 空间复杂度：$O(1)$，只使用了少量变量。

这里的 $n$ 不是输入数组长度，而是我们主动设置的采样次数。采样次数越大，结果越稳定，但运行时间越长；采样次数越小，运行越快，但误差可能越大。这是蒙特卡罗算法中精度与效率的权衡。

7. 为什么采样越多越准确#

蒙特卡罗算法依赖的是概率统计中的大数定律。

当采样次数较少时，随机结果波动较大。例如只生成 $10$ 个点，可能恰好有 $7$ 个落在圆内：

误差很大。但如果生成 $1000000$ 个点，落在圆内的比例会更稳定，更接近真实概率 $\frac{\pi}{4}$，估算出的 $\pi$ 也会更接近真实值。

不过需要注意：

采样次数增加，只能让结果更稳定，并不能保证每一次都精确等于真实答案。

这也是蒙特卡罗算法和确定性算法的本质区别。

8. 总结#

蒙特卡罗算法的核心是：

用大量随机实验的统计结果，去近似真实答案。

在估算圆周率 $\pi$ 的例子中，我们利用了圆和正方形的面积比例 $\frac{\pi}{4}$，通过随机点落入圆内的比例来估算：

蒙特卡罗算法思路简单、容易实现，尤其适合难以精确计算的问题，比如高维积分、复杂系统模拟和概率估计。但它的结果带有随机性，通常只能得到近似答案，且精度依赖采样次数。

口诀

随机撒点，统计比例，用概率逼近答案。