递归时间复杂度要乘二吗
1个回答
展开全部
用主方法求递归程序的时间复杂度，再看看相关资料:
T(n)=aT(n/b)+f(n)
其中a=2，b=4，f(n)=√n，logb(a)=1/2，
而n^logb(a)=√n
因此T(n)=√n*logb(n)=√n*log4(n)
也就是√n*logn，选C
T(n)=aT(n/b)+f(n)
其中a=2，b=4，f(n)=√n，logb(a)=1/2，
而n^logb(a)=√n
因此T(n)=√n*logb(n)=√n*log4(n)
也就是√n*logn，选C
追问
所以说这一步是因为递归乘二还是属于log(n)级别？？ T(n)=√n*logb(n)=√n*log4(n)
追答
时间复杂度是忽略系数的。再说这中间有比较复杂的推倒过程，这个√n是从n^logb(a)求出来的，也不是乘不乘2的问题啊。。。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
