美文网首页
二项式分布算法(Java实现)

二项式分布算法(Java实现)

作者: jeff98 | 来源:发表于2018-08-26 19:46 被阅读0次

二项式分布算法(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),而且有一部分计算是不需要的(有些“空”不需要填)

相关文章

网友评论

      本文标题:二项式分布算法(Java实现)

      本文链接:https://www.haomeiwen.com/subject/vstaiftx.html