C ++二项式系数太慢 [英] C++ Binomial Coefficient is too slow

问题描述

我试图通过对Pascal三角形进行递归来计算二项式系数.它适用于少量数字，但是20以上的速度真的很慢，或者根本不起作用.

I've tried to compute the binomial coefficient by making a recursion with Pascal's triangle. It works great for small numbers, but 20 up is either really slow or doesn't work at all.

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

I've tried to look up some optimization techniques, such as "chaching" but they don't really seem to be well integrated in C++.

如果可以的话，这是代码.

Here's the code if that helps you.

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;

}

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

My guess is that the programm wastes a lot of time calculating results it has already calculated. It somehow must memorize past results.

推荐答案

我的猜测是该程序浪费了很多时间来计算已经计算出的结果.

My guess is that the program wastes a lot of time calculating results it has already calculated.

那是真的.

关于此主题，建议您查看动态编程主题.

On this topic, I'd suggest you have a look to Dynamic Programming Topic.

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

There is a class of problem which requires an exponential runtime complexity but they can be solved with Dynamic Programming Techniques. That'd reduce the runtime complexity to polynomial complexity (most of the times, at the expense of increasing space complexity).

动态编程的常用方法是:

• 自顶向下(利用记忆和递归).
• 自下而上(迭代).

• Top-Down (exploiting memoization and recursion).
• Bottom-Up (iterative).

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

Following, my bottom-up solution (fast and compact):

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). 确实，这是线性的.

This algorithm has a runtime complexity O(k) and space complexity O(k). Indeed, this is a linear.

此外，此解决方案比递归方法更简单，更快捷. CPU缓存友好.

Moreover, this solution is simpler and faster than the recursive approach. It is very CPU cache-friendly.

请注意，也没有对n的依赖.

Note also there is no dependency on n.

我通过简单的数学运算并获得以下公式获得了此结果:

I have achieved this result exploiting simple math operations and obtaining the following formula:

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

关于二项式系数的一些数学参考.

注意

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

The algorithm does not really need a space complexity of O(k). Indeed, the solution at i-th step depends only on (i-1)-th. Therefore, there is no need to store all intermediate solutions but just the one at the previous step. That would make the algorithm O(1) in terms of space complexity.

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

However, I would prefer keeping all intermediate solutions in solution code to better show the principle behind the Dynamic Programming methodology.

这里的存储库具有优化算法

这篇关于C ++二项式系数太慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！