二项式分布算法(Java实现)
最近开始看《算法(第四版)》,这是遇到的第一个算法题。题目要求的只是估计一下算法递归的次数,但我进一步研究了不同的计算二项式分布的算法。
二项式分布简介
这里就不过多展开,以自己的语言解释一下。
某一个实验出现事件的概率为, 且重复该实验结果不相互干扰(独立)
求重复次该实验时,出现k次事件的概率:
上式即为本博客探讨的问题
利用二项式公式实现 V1.0
学数学时候比较熟悉的公式就是
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中的一个问题:当计算 的时候,有两个方式:
这两个方式的运算量不相同,在具体运算时可以进行选择
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
这是示例的代码,在官网可以查看
其基本思想是:
将大问题逐次拆分为小问题的递归思想
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];
}
此方法虽然巧妙,但其实速度上比不过公式法(复杂度达到,而且有一部分计算是不需要的(有些“空”不需要填)
网友评论