C++ 二项式系数太慢

我试图通过使用帕斯卡三角形进行递归来计算二项式系数。它适用于较小的数字，但 20 up 要么非常慢，要么根本不起作用。

我试图查找一些优化技术，例如“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;

}

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

最佳答案

这绝对是真的。

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

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

动态规划的常用方法是:

自上而下(利用内存和递归)。

自下而上(迭代)。

以下是我的自下而上的解决方案(快速且紧凑):

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) 步。
因此，不需要存储所有中间解决方案，而只需存储上一步的解决方案。这将使算法 O(1) 在空间复杂度方面。

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

Here my repository with the optimized algorithm 。

关于C++ 二项式系数太慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55421835/