c – 用于计算二项式系数的递归算法的时间复杂度
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c – 用于计算二项式系数的递归算法的时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1473字，纯文字阅读大概需要3分钟。
内容图文
我正在研究算法复杂性分析.我有不整合的问题或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) with T(n,n) = T(n,0) = O(1)
显然,n每步减少一个.如果我们忽略(只是暂时)存在参数k,基本上每个步骤的调用次数加倍.这种情况发生了n次,直到n = 1.现在C(1,k)返回1.所以你最多调用C(n,k)2n次.所以C(n,k)在O(2n)中.
现在我们记住了k.什么是k的最坏情况？也许k = n / 2(对于偶数n).你可以看到你需要至少n / 2步,直到k达到1或n在任何递归调用中达到n / 2.所以通话次数增加了两倍至少2n / 2次.但是还有更多的电话.写下来是相当多的工作.
编辑1
让我们来看看这张照片
你开始调用C(n,n / 2)(n = 6).灰色三角形是包含在n / 2“步”中的部分,直到您首先到达角(C(n,0)或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’s triangle的连接.
一个小技巧
算法C(n,k)通过加1来计算Binomial coefficient.通过使用Stirling’s approximation你可以看到,C(n,n / 2)&大约; 2n / sqrt(n)(省略了一些常量以简化).
因此算法必须添加许多1,因此它具有O(2n / sqrt(n))的复杂度.
内容总结
以上是互联网集市为您收集整理的c – 用于计算二项式系数的递归算法的时间复杂度全部内容，希望文章能够帮你解决c – 用于计算二项式系数的递归算法的时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。