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

我正在研究算法复杂性分析。我有不合格问题或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)?

您正在寻找的复发是

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

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ⁿ).

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^n/2 times. But there are many more calls. Writing it down is quite a bit of work.

Edit 1那么我们来看看这张照片

您开始调用 C(n,n/2)（n=6）。灰色三角形是包含在 n/2 个“台阶”中直到到达拐角的部分（C(n,0) 或 C(n,n)）first。但正如您所看到的，有更多的电话。我用蓝色框标记了递归停止的调用，并用绿色数字写下了调用特殊 C(n,k) 的数字。

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

Edit 3由于一次 C(n,k) 调用中的所有操作都在 O(1)（恒定时间）内运行，因此我们只需计算调用次数即可获得复杂性。注意：如果 C(n,k) 包含一个在 O(n) 中运行的操作，我们必须将调用次数乘以 O(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)).