递归时间复杂度要乘二吗
发布网友
发布时间：2022-05-14 14:34
共1个回答
热心网友
时间：2023-07-29 20:58
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的问题啊。。。
