二项式分布算法（Java实现）：题目、思路与代码实现。

二项式分布算法（Java实现）

最近开始看《算法(第四版)》，这是遇到的第一个算法题。题目要求的只是估计一下算法递归的次数，但我进一步研究了不同的计算二项式分布的算法。

二项式分布简介

这里就不过多展开，以自己的语言解释一下。

某一个实验出现事件\(A\)的概率为\(p\), 且重复该实验结果不相互干扰（独立）

求重复\(N\)次该实验时，出现k次事件\(A\)的概率：

\[P(X=k;N,p)\]

上式即为本博客探讨的问题

利用二项式公式实现 V1.0

学数学时候比较熟悉的公式就是

\[P(X=k;N,p) = C_N^k \times p^k \times (1-p)^{N-k}\]

public static double myBinomial(int N, int k, double p) {
    long c = N;
    for(int i = N-1; i >= N-k+1; --i)
        c*=i;
    for(int i = 2; i <= k; ++i)
        c/=i;
    double a1 = Math.pow(p, k);
    double a2 = Math.pow(1-p, N-k);
    return c*a1*a2;
}

改进版 V1.1

改进版本聚焦V1.0中的一个问题：当计算 \(C_N^k\)的时候，有两个方式：

1. \(\large{C_N^k = \frac{N!}{k!(N-k)!} = \frac{N(N-1)\cdots(k+1)}{(N-k)(N-k-1)\cdots2}}\)
2. \(\large{C_N^k = \frac{N!}{k!(N-k)!} = \frac{N(N-1)\cdots(N-k+1)}{k(k-1)\cdots2}}\)

这两个方式的运算量不相同，在具体运算时可以进行选择

public static double myBinomial2(int N, int k, double p) {
    long c = N;
    if(k < N-k) {
        for(int i = N-1; i >= N-k+1; --i)
            c*=i;
        for(int i = 2; i <= k; ++i)
            c/=i;
    }
    else {
        for(int i = N-1; i >= k+1; --i)
            c*=i;
        for(int i = 2; i <= N-k; ++i)
            c/=i;
    }
    double a1 = Math.pow(p, k);
    double a2 = Math.pow(1-p, N-k);
    return c*a1*a2;
}

利用递归实现 V2.0

这是示例的代码，在官网可以查看

其基本思想是：

\[P(X=k;N,p) = p\times P(X=k-1;N-1,p) + (1-p)\times P(X=k;N-1,p)\]

将大问题逐次拆分为小问题的递归思想

public static double binomial1(int N, int k, double p) {
    if (N == 0 && k == 0) return 1.0;
    if (N < 0 || k < 0) return 0.0;
    return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
}

将递归改进为迭代 V2.1

这里的方法挺巧妙的！
将递归的步骤“逆”过来，变成了“填格子”——递归自上而下，该方法则化为自下而上的迭代法。

public static double binomial2(int N, int k, double p) {
        double[][] b = new double[N+1][k+1];

        // base cases
        for (int i = 0; i <= N; i++)
            b[i][0] = Math.pow(1.0 - p, i);
        b[0][0] = 1.0;

        // recursive formula
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= k; j++) {
                b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];
                StdOut.printf("%f\t", b[i][j]);
            }
            StdOut.println();
        }
        return b[N][k];
    }

此方法虽然巧妙，但其实速度上比不过公式法(复杂度达到\(O(N^2)\)，而且有一部分计算是不需要的（有些“空”不需要填）

---

本文最初发布于简书。

Donate