C ++二项式系数太慢了

Question

我试图通过使用Pascal三角形进行递归来计算二项式系数。它对于小数字很有用，但是20上升要么非常慢，要么根本不起作用。

我试图查找一些优化技术，例如“chaching”，但它们似乎并没有很好地集成在C ++中。

这是代码，如果这有助于你。

int binom(const int n, const int k)
{
    double sum;

    if(n == 0 || k == 0){
            sum = 1;
    }
    else{
    sum = binom(n-1,k-1)+binom(n-1,k);
    }

    if((n== 1 && k== 0) || (n== 1 && k== 1))
       {
           sum = 1;
       }
    if(k > n)
    {
        sum = 0;
    }

    return sum;

}

int main()
{
int n;
int k;
int sum;

cout << "Enter a n: ";
cin >> n;
cout << "Enter a k: ";
cin >> k;

Summe = binom(n,k);

cout << endl << endl << "Number of possible combinations: " << sum << 
endl;

}

我的猜测是该程序浪费了大量时间来计算已经计算过的结果。它必须以某种方式记住过去的结果。

Answer 1

我的猜测是该程序浪费了大量时间来计算已经计算过的结果。

这绝对是真的。

关于这个话题，我建议你看看Dynamic Programming Topic。

存在一类需要指数运行时复杂性的问题，但它们可以通过动态编程技术来解决。这会将运行时复杂性降低到多项式复杂度（大多数情况下，代价是增加空间复杂性）。

---

动态编程的常用方法是：

• 自上而下（利用memoization和递归）。
• 自下而上（迭代）。

以下，我自下而上的解决方案（快速和紧凑）：

int BinomialCoefficient(const int n, const int k) {
  std::vector<int> aSolutions(k);
  aSolutions[0] = n - k + 1;

  for (int i = 1; i < k; ++i) {
    aSolutions[i] = aSolutions[i - 1] * (n - k + 1 + i) / (i + 1);
  }

  return aSolutions[k - 1];
}

该算法具有运行时复杂度O(k)和空间复杂度O(k)。实际上，这是线性的。

而且，这种解决方案比递归方法更简单，更快捷。它非常适合CPU缓存。

另请注意，n没有任何依赖性。

我利用简单的数学运算并获得以下公式实现了这个结果：

(n, k) = (n - 1, k - 1) * n / k

Some math references on the Binomial Coeffient。

---

注意

该算法并不真正需要O(k)的空间复杂度。实际上，第i步的解决方案仅取决于（i-1）-th。因此，不需要存储所有中间解决方案，只需存储上一步骤中的解决方案。这将使算法O(1)在空间复杂性方面。

但是，我更希望将所有中间解决方案保留在解决方案代码中，以更好地展示动态编程方法背后的原理。

Here my repository with the optimized algorithm。

Answer 2

我会在地图中缓存每个计算的结果。您无法使用复杂的密钥创建地图，但您可以将密钥转换为字符串。

string key = string("") + n.to_s() + "," + k.to_s();

然后有一张全球地图：

map<string, double> cachedValues;

然后，您可以使用密钥进行查找，如果找到，则立即返回。否则在您返回之前，请存储到地图中。

我开始绘制调用4,5会发生什么。它变得很乱，有很多计算。每个级别更深层导致2 ^ n个查找。

我不知道您的基本算法是否正确，但如果是这样，那么我将此代码移到方法的顶部：

if(k > n)
{
    return 0;
}

因为看起来如果k> n，你总是返回0，即使是像6,100这样的东西。但是，我不知道这是否正确。

Answer 3

您正在多次计算一些二项式值。快速解决方案是记忆。

未经测试：

int binom(int n, int k);

int binom_mem(int n, int k)
{
    static std::map<std::pair<int, int>, std::optional<int>> lookup_table;
    auto const input = std::pair{n,k};
    if (lookup_table[input].has_value() == false) {
        lookup_table[input] = binom(n, k);
    }
    return lookup_table[input];
}

int binom(int n, int k)
{
    double sum;

    if (n == 0 || k == 0){
        sum = 1;
    } else {
        sum = binom_mem(n-1,k-1) + binom_mem(n-1,k);
    }

    if ((n== 1 && k== 0) || (n== 1 && k== 1))
    {
        sum = 1;
    }
    if(k > n)
    {
        sum = 0;
    }

    return sum;
}

一个更好的解决方案是转换递归tailrec（双递归不容易）或更好，但根本不使用递归;）