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

Question

我正在研究算法复杂性分析.我有不整合的问题或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)？

Answer 1

你正在寻找的复发是

T(N,K)= T(N-1,K)+ T(N-1,K-1)+ O(1)其中T(N,N)= T(N,0)= O(1)

显然,n每步减少一个.如果我们忽略(只是暂时)存在参数k,基本上每个步骤的调用次数加倍.这种情况发生了n次,直到n = 1.现在C(1,k)返回1.所以你最多调用C(n,k)2 ⁿ次.所以C(n,k)在O(2 ⁿ)中.

现在我们记住了k.什么是k的最坏情况？也许k = n/2(对于偶数n).你可以看到你需要至少n/2步,直到k达到1或n在任何递归调用中达到n/2.因此,通话次数增加了至少2 ^n/2次.但是还有更多的电话.写下来是相当多的工作.

编辑1 所以让我们来看看这张照片

你开始调用C(n,n/2)(n = 6).灰色三角形是包含在第n/2"台阶",直到到达角(C(N,O)或C(N,N))的部分第一.但正如你所看到的,还有更多的电话.我标记了调用,递归在一个蓝色框中停止,并写了一个特殊的C(n,k)被调用,带有绿色数字.

编辑2 C(n,k)的值和返回值1的C(n,k)的调用次数是相同的,因为函数只返回值1(或递归调用的结果) ).在示例中,您会看到蓝色框中写入的绿色数字的总和(即调用次数)总计为20,这也是C(6,3)的值.

编辑3由于一个C(n,k)调用中的所有操作都在O(1)(常量时间)中运行,因此我们只需要对调用进行计数以获得复杂性.注意:如果C(n,k)包含在O(n)中运行的操作,我们必须将调用次数乘以O(n)以获得复杂性.

您还会注意到与Pascal三角形的连接.

一个小技巧

算法C(n,k)通过加1来计算二项式系数.通过使用斯特灵公式,你可以看到,C(N,N/2)≈2 ^ñ /开方(N)(遗漏了一些常数简化).因此算法必须添加许多1,因此它具有O(2 ⁿ/sqrt(n))的复杂度.