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

问题描述

我正在研究算法复杂度分析。我遇到不符合项或 C（n，k）的问题。

I'm studying about algorithm complexity analysis. I have problem with unconformity or 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）？

How can I determine its execution complexity or T(n)?

推荐答案

您要查找的重复出现次数是

The recurrence you are looking for is

很显然，n每步减少1。如果我们暂时忽略参数k，那么调用的数量基本上每步都会翻倍。这会发生n次，直到n =1。现在C（1，k）返回1。因此，您最多可以调用C（n，k）2 次。所以C（n，k）在O（2 ）中。

Obviously n is decreased by one every step. If we ignore (just for the moment) that there is a parameter k, basically the number of calls doubles every step. This happens n times, until n = 1. Now C(1,k) returns 1. So you call C(n,k) at most 2 times. So C(n,k) is in O(2).

现在我们记住了k。对于k，最坏的情况是什么？也许k = n / 2（对于偶数n）。您可以看到至少需要n / 2个步骤，直到在任何递归调用中k达到1或n达到n / 2为止。因此，通话次数至少翻了一番，至少2 次。但是还有更多的电话。写下来需要很多工作。

Now we remember the k. What would be a worst case for k? maybe k = n/2 (for an even n). You can see that you need at least n/2 steps until k reaches 1 or n reaches n/2 in any recursive call. So the number of calls doubles at least 2 times. But there are many more calls. Writing it down is quite a bit of work.

编辑1
因此，让我们看一下这张图片

Edit 1So lets take a look at this picture

您开始调用C（n，n / 2）（n = 6）。灰色三角形是n / 2个步骤中包含的部分，直到您到达角（C（n，0）或C（n，n）） first 。但是如您所见，还有更多的电话。我标记了这些调用，其中递归以一个蓝色框停止，并用绿色数字写了一个特殊的C（n，k）调用号。

You start calling C(n,n/2) (with n=6). The grey triangle is the part that is contained in the n/2 "steps" until you reach the corner (C(n,0) or C(n,n)) first. But as you can see, there are more calls. I marked the calls, where the recursion stops with a blue box and wrote the number a special C(n,k) is called, with a green number.

编辑2 C（n，k）的值和返回值1的C（n，k）的调用次数相同，因为该函数仅返回值1（或a）。递归调用的结果）。
在该示例中，您看到写在蓝色框上的绿色数字的总和（即调用次数）总计为20，这也是C（6,3）的值。

Edit 2 The value of C(n,k) and the number of calls of C(n,k), that return the value 1, are the same, since the function return only the value 1 (or a result of a recursive call).In the example you see that the sum of the green numbers written at the blue boxes, which are the number of calls, sums up to 20 which is also the value of C(6,3).

编辑3 由于一次C（n，k）调用中的所有操作均以O（1）（恒定时间）运行，因此我们只有计算通话次数以获取复杂性。注意：如果C（n，k）包含在O（n）中运行的运算，则必须将调用次数乘以O（n）才能获得复杂性。

Edit 3 Since all operations in one C(n,k) call run in O(1) (constant time), we only have to count the calls to get the complexity. Notice: If C(n,k) would contain an operation that runs in O(n), we would have to multiply the number of call by O(n) to get the complexity.

您还将注意到与。

算法C（n，k）计算加1。通过使用，您可以看到C（n，n / 2）&approximated; 2 / sqrt（n）（为简化起见，省略了一些常量）。
因此，该算法必须添加多个1，因此其复杂度为O（2 / sqrt（n））。

The algorithm C(n,k) computes the Binomial coefficient by adding 1's. By using Stirling's approximation you can see, that C(n,n/2) ≈ 2/sqrt(n) (left out some constants for simplification).So the algorithm has to add that many 1's and so it has a complexity of O(2/sqrt(n)).

这篇关于计算二项式系数的递归算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！