题答科教解疑网 _ www.97td.cn
首页 校园生活 人文学科 理工学科 外语学习 学习帮助 招生考试 资格考试 考研相关 公务员 留学 建筑学 心理学 农业科学 物理学 职业培训 自考 高考 其它学科
栏目导航
首页 > 学习帮助 > 正文

能有思路最好啦,分析以下算法的时间复杂度,谢谢啦

作者:用户发布来源:题答科教解疑网发布时间:2019/5/16


能有思路最好啦哎也,分析以下算法的时间复杂度,谢谢啦

每当调用这个函数时会产生2个递归分支,所以时间复杂度是O(2^n)。 n==1时,以此类推,4次rec(1),2次rec(2),调用1次rec(3),调用1次rec(1),2次rec(1), n==3时, n==2时,调用1次rec(2),总的调用次数为2^0+2^1+2^2++2^(n-1)=2^n-1,因为函数内不存在循环,T(n)=(2^n-1)*1=2^n-1,存在正的常数c,n0使得对于任意n>=n0时有T(n)<=c*2^n,所以这个时间复杂度是O(2^n)。


更多话题
上一篇:希望可以有思路最好了,分析以下算法的时间复杂度,谢谢 下一篇:我长大了要做老师作文如何第写
[题答科教解疑网 _ www.97td.cn] 本站信息来自网友发布,本站无法保证其内容真实性,请用户一定仔细辨别。联系QQ:885 971 98