算法第四版：1.1.27 二项分布，从100到100亿@TOC

递归法实现二项分布运算，O(2^N)

递归实现的算法，相对来说非常简单，对于参数比较小的情况，非常适合。

但问题也比较明显，N * k > 100开始就非常慢，当>1000程序基本崩溃。算法效率O(2^N)，基本不能用于实际开发。

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

通过将计算结果保存到数组中，进行优化，O(N)

同样是递归，但将已计算结果保存复用，复杂度立刻降低，效率O(N)。

此时可以进行较大数运算，例如N * k =100,000,000，已经可以用于实践，再大意义不大。

struct bino
{
    double qbinomial(int N, int k, double p)
    {
        if (N == 0 && k == 0)
        {
            return 1;
        }
        if (N < 0 || k < 0)
        {
            return 0;
        }
        vd = std::vector<std::vector<double>>((N + 1), std::vector<double>((k + 1), -1));

        return qbinomial(0, N, k, p);
    }
    
private:
    double qbinomial(int f, int N, int k, double p)
    {
        if (N == 0 && k == 0)
        {
            return 1;
        }
        if (N < 0 || k < 0)
        {
            return 0;
        }
        if (vd[N][k] < 0)
        {
            vd[N][k] = (1.0 - p) * qbinomial(0, N - 1, k, p) + p * qbinomial(0, N - 1, k - 1, p);
        }
        double result = vd[N][k];
        vd.clear();
        return result;
    }
    
    std::vector<std::vector<double>> vd;
};

追求至善，寻求突破

用优化递归，数量级再加一，程序崩溃，为提高稳定性，弃用递归法，改用循环，但是需要对算法有深入了解。

递归是从后向前推，占用计算量还是太大。直接从数组循环推进，稳定性得以改善。在N * k =5亿级别，不崩了，但是速度没有显著提高。

    double qqbinomial(int N, int k, double p) //快速二项分布；构建矩阵数据结构
    {
        if (N == 0 && k == 0)
        {
            return 1;
        }
        if (N < 0 || k < 0)
        {
            return 0;
        }
        std::vector<std::vector<double>> qvd = 
                 std::vector<std::vector<double>>
                         ((N + 1), std::vector<double>((k + 1), 0));
        double q = 1;
        for (size_t i = 0; i != N + 1; ++i)
        {
            qvd[i][0] = q;
            q *= 1 - p;
        }

        double pp = 1 - p;
        for (size_t i = 1; i != N + 1; ++i)
        {
            if (i < k) //当i > k 时，多出的部分值都是0，做判断避免重复计算
            {
                for (size_t j = 1; j != i + 1; ++j)
                {
                    qvd[i][j] = pp * qvd[i - 1][j] + p * qvd[i - 1][j - 1];
                }
            }
            else
            {
                for (size_t j = 1; j != k + 1; ++j)
                {
                    qvd[i][j] = pp * qvd[i - 1][j] + p * qvd[i - 1][j - 1];
                }
            }
        }
        double result = qvd[N][k];
        qvd.clear();
        return result;
    }

我要极致的稳定性

如何才能够达到C++的 int 上限？当 N * k =10亿，内存不够仍然崩溃，但这还未达到int整型的上限。

我能达到上限么？大概不行，但要尝试。

回顾循环数组算法，发现，数组的元素个数为N * k，当数量突破10亿，16g的内存直接崩溃。但我需要如此大的数组么？

问题出在数据结构上。 算法在推算数值时，只需要[ N - 1] [ k ]以及[ N - 1 ] [ k - 1 ] 两个数，这两个数需要k个数，所以可以采用 std::deque<std::vector< double >> 数据结构，每计算并插入一行数组，就从队列的顶部移除一个数组，此时占用的内存不会超过 k个double型 的内存。

同时，根据算法得出，k > N 时结果为0，可以将算法效率提升至 O(N)或O(1) ，同时内存空间不大于 k个double类型所占内存。

此时，数量级N * K 可以达到100亿，理论上突破到int上限（20亿），但已经没有什么意义。

以下是代码：

    double binomial(int N, int k, double p) //稳定二项分布，构建队列
    {
        if (N == 0 && k == 0)
        {
            return 1;
        }
        if (N < 0 || k < 0)
        {
            return 0;
        }
        if (k > N)
        {
            double result = 0;
            return result;
        }

        std::deque<std::vector<double>> deqVecDou;
        deqVecDou.push_back(std::vector<double>{1, 0});

        double q = 1;
        std::vector<double> lieOne(N + 1);
        for (size_t i = 0; i != N + 1; ++i)
        {
            lieOne[i] = q;
            q *= 1 - p;
        }

        double pp = 1 - p;
        for (size_t i = 1; i != N + 1; ++i)
        {
            if (i < k)
            {
                deqVecDou.push_back(std::vector<double>(i + 2, 0));
                deqVecDou[1][0] = lieOne[i];
                for (size_t j = 1; j != i + 1; ++j)
                {
                    deqVecDou[1][j] = pp * deqVecDou[0][j] + p * deqVecDou[0][j - 1];
                }
                deqVecDou.pop_front();
            }
            else
            {
                deqVecDou.push_back(std::vector<double>(k + 2, 0));
                deqVecDou[1][0] = lieOne[i];
                for (size_t j = 1; j != k + 1; ++j)
                {
                    deqVecDou[1][j] = pp * deqVecDou[0][j] + p * deqVecDou[0][j - 1];
                }
                deqVecDou.pop_front();
            }
        }
        double result = deqVecDou[0][k];
        deqVecDou.clear();
        lieOne.clear();
        return result;
    }

算法在没有数据结构的基础上，基本就是空中楼阁。

这个《算法》第四版第一章第一节的小题，让我花了两天时间思考，改善，虽说是瞎整，因为最后已经超出实际需求，且double的数据精度已经远远的被抛下，但还是有意义的。

从O(2^N)推进到O(N)，只需要配合最基本的数组。而内存占用从N ^ 2 到 N，只需要队列套个数组，然后循环顶部删除。深刻体会到，算法的打击是碾压级别的，以追求效率著称的C++，如果没有算法的加持，基本就是个笑话。

有关算法，请看这里：
二项分布（1.1.27 Binomial distribution）的递归算法，基于数组进行改进