使用数组来提高递归二项分布算法的执行时间？

Question

作为一个初学者，我最近购买了罗伯特•塞奇威克/凯文•韦恩的《算法-第四版》一书，并且很欣赏每章末尾的练习题。然而，在其中有一个看起来相当简单的练习题却让我疯狂，因为我找不到解决方法。

你需要采取这个递归算法，它可以在n次试验中找到成功k次的概率，其中p是一次事件成功的概率。所给出的算法基于递归二项式分布公式。

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

这个练习的目标是通过在数组中保存计算的值，使这个算法更快。我已经通过使用另一种获取二项式分布 [p(x) = nCr * p^k * (1 - p)^(n - k)] 的方法（使用迭代方法来查找阶乘），使得该算法变得相当快。但是，我不明白在这种情况下如何使用数组来提高执行时间。

非常感谢任何帮助！

...在有人问之前，这不是作业！

- user1311189

---

你的递归是否需要重新计算已经有的任何数字？如果是这样，通过保存这些数字，您可以直接引用它们，而不必再次计算它们。 - twain249

如果这不是作业，你应该使用二项分布的闭式形式版本：http://en.wikipedia.org/wiki/Binomial_distribution - ControlAltDel

Answer 1

这本书试图教你一种特定的编程技术，称为记忆化，它是一种更广泛的技术，被称为动态规划。当然，在现实生活中，知道一个闭合形式的解决方案要好得多，但在解决这个练习的情况下不是这样。无论如何，想法是将一个二维数组作为第四个参数传递，最初用NaN填充它，并检查数组中是否有给定组合的n和k的解决方案，如果有，则返回它；如果没有，则递归计算，存储在数组中，然后再返回它。

- Sergey Kalinichenko

---

所以，不要每次都进行计算，先检查一下我们是否已经知道了它。对吗？ - Ismael

值得注意的是，实际上您不需要一个2D数组来存储这些值。如果您使用迭代从n = 0开始系统地计算值，而不是使用递归从所需的n向下计算，那么避免使用它会更容易。（由于历史原因，当涉及到这种迭代结构时，术语“动态规划”更常用，而在涉及递归方法时则使用“记忆化”。两者通常是等效的。） - Gareth McCaughan

@ismaelga 是的，这就是记忆化技术背后的思想。本质上，你用内存来换取计算速度的提升。 - Sergey Kalinichenko

@GarethMcCaughan 你说得完全正确。如果通过采用DP来优化内存，那么我不会感到惊讶，这可能会在本书的后面作为一项练习出现。 - Sergey Kalinichenko

Answer 2

这里的递归算法最终会反复调用特定的条件。例如：

3, 3
  2, 3
    1, 3
      0, 3
      0, 2
    1, 2
      0, 2
      0, 1
  2, 2
    1, 2
      0, 2
      0, 1
    1, 1
      0, 1
      0, 0

通过记住例如(1,2)的值，当再次使用这些参数调用时立即返回，可以使其更有效率。使用Guava的Table，代码如下：

public static double binomial(int n, int k, double p, Table<Integer, Integer, Double> memo) {
    if(memo.contains(n, k))
        return memo.get(n, k);

    double result;
    if (n == 0 && k == 0)
        result = 1.0;
    else if (n < 0 || k < 0)
        result = 0.0;
    else 
        result = (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);

    memo.put(n, k, result);
    return result;
}

- Russell Zahniser

Answer 3

有点晚了，但对于那些正在寻找完整解决方案的人，下面是我的方法。首先建议其他人阅读此处提供的答案：https://dev59.com/LG025IYBdhLWcg3wLizo#6165124 以了解动态规划、记忆化和表格化的含义。

关于我的解决方案，基本上我们有以下给定方法：

// Not efficient at all
private static double binomial(int N, int k, double p)
{
    if (N == 0 && k == 0)
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else
    {
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
}

是的，这确实很慢……递归调用的次数相当大（大约~N^2）。

是的，你可以使用记忆化方法，基本上就是像其他人已经说过的一样，缓存已经计算过的值。 对于一些人来说，记忆化意味着保留递归策略并检查我们需要的值是否已经被计算过，如果没有，则程序必须计算并缓存它，这很容易实现。

private static double binomialTopDown(int N, int k, double p)
{
    double[][] cache = new double[N + 1][k + 1];

    for (int i = 0; i < (N + 1); i++)
    {
         Arrays.fill(cache[i], Double.NaN);
    }

    return binomialTopDown(N, k, p, cache);
}

// More efficient
private static double binomialTopDown(int N, int k, double p, double[][] cache)
{
    if ((N == 0) && (k == 0))
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else if (Double.isNaN(cache[N][k]))
    {
        cache[N][k] = (1.0 - p) * binomialTopDown(N - 1, k, p, cache) + p * binomialTopDown(N - 1, k - 1, p, cache);
    }

    return cache[N][k];
}

使用自底向上的方法（也称为表格法），以更加高效的方式对计算进行排序，这通常通过使用上述算法的迭代版本来实现。

// Much more efficient
private static double binomialBottomUp(int N, int k, double p)
{
    /*
    double[][] cache = new double[N + 1][k + 1];

    cache[0][0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        cache[i][0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            cache[i][j] =  p * cache[i - 1][j - 1] + (1.0 - p) * cache[i - 1][j];
        }
    }

    return cache[N][k];
    */

    // Optimization using less memory, swapping two arrays
    double[][] cache = new double[2][k + 1];
    double[] previous = cache[0];
    double[] current = cache[1];
    double[] temp;

    previous[0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        current[0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            current[j] =  p * previous[j - 1] + (1.0 - p) * previous[j];
        }

        temp = current;
        current = previous;
        previous = temp;
    }

    return previous[k];
}

希望你能使用自底向上的动态规划方法，以最高效的方式完成此任务。

希望这有所帮助。

- Natalie Perret