递归算法计算二项式系数的时间复杂度

Question

递归算法计算二项式系数的时间复杂度

c++recursioncomplexity-theorytime-complexity

8

我正在学习算法复杂度分析。我遇到了与不一致或C(n, k)有关的问题。

int C(int n, int k){
   if(n==k || k==0)
     return 1;
   return C(n-1, k) + C(n-1, k-1);
}

我如何确定它的执行复杂度或 T(n)？

- Andiana

2

步骤1：编写递归。 - David Eisenstat

抱歉，我不明白，请您再说得更清楚一些。 - Andiana

我的意思是，编写方程式 T(n, k)，使得 T(n, k) 是 C(n, k) 运行时间的大O符号。 - David Eisenstat

我认为T(n)是：如果(n== - Andiana

1

我想你的意思是 if(n==k || k==0)？少了一个 0。 - AbcAeffchen

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AbcAeffchen · Accepted Answer

您要查找的递归式为：

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1) 其中 T(n,n) = T(n,0) = O(1)

显然，每一步n都会减少1。如果我们暂时忽略参数k，基本上每一步调用次数会翻倍。这种情况会发生n次，直到n=1。现在C(1,k)返回1。因此，最多调用C(n,k) 2ⁿ次。因此，C(n,k)是O(2ⁿ)。

现在我们记住了k。k的最坏情况会是什么？也许k=n/2（对于偶数n）。您可以看到，直到任何递归调用中k达到1或n达到n/2，至少需要n/2步。因此，调用次数至少会增加2^n/2次。但是还有更多的调用。写下来需要相当多的工作。 Edit 1：所以让我们看看这张图片。

pascal's triangle with number of calls and arrows

您开始调用C(n,n/2)（其中n=6）。灰色三角形是包含在到达角落（C(n,0)或C(n,n)）之前的n/2“步骤”中的部分。但是，正如您所看到的，还有更多的调用。我用蓝色框标记了递归停止的调用，并写下了绿色数字调用的特殊C(n,k)的数量。 编辑2 C(n,k)的值和调用返回值1的次数相同，因为函数仅返回值1（或递归调用的结果）。在示例中，您可以看到在蓝色框中写的绿色数字之和为20，这也是C(6,3)的值。 编辑3 由于一个C(n,k)调用中的所有操作都在O(1)（常数时间）内运行，因此我们只需要计算调用次数即可得到复杂度。注意：如果C(n,k)包含一个运行时间为O(n)的操作，则必须将调用次数乘以O(n)才能得到复杂度。

你还会注意到与Pascal's triangle的关联。

一个小技巧

算法C(n,k)通过添加1来计算二项式系数。通过使用Stirling's approximation近似值，你可以看到C(n,n/2) ≈ 2ⁿ/sqrt(n)（为简化省略了一些常量）。因此，该算法必须添加那么多1，因此它的复杂度为O(2ⁿ/sqrt(n))。