我尝试通过帕斯卡三角形进行递归来计算二项式系数。它对于小数量来说效果很好,但是 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;
}
我的猜测是该程序浪费了大量时间来计算它已经计算出的结果。它必须以某种方式记住过去的结果。
我的猜测是该程序浪费了大量时间来计算它已经计算出的结果。
这绝对是真的。
关于这个话题,我建议你看看动态规划主题.
有一类问题需要指数级的运行时复杂度,但可以用以下方法解决动态规划技术。
这会将运行时复杂度降低到多项式复杂度(大多数时候,以增加空间复杂度为代价)。
常见的方法为动态规划 are:
-
Top-Down(利用记忆和递归)。
-
自下而上(迭代)。
接下来,我的自下而上解决方案(快速且紧凑):
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
关于二项式系数的一些数学参考.
Note
该算法实际上并不需要空间复杂度O(k)
。
事实上,解决方案在i-th步骤仅取决于(i-1)-th。
因此,不需要存储所有中间解,只需存储上一步的中间解即可。这将使算法O(1)
在空间复杂度方面。
但是,我更愿意将所有中间解决方案保留在解决方案代码中,以更好地展示背后的原理动态规划方法.
这是我的带有优化算法的存储库.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)