返回信息流public class digui {
public int test(int n){
if(n==1) return 1;
return 2*test(n/2)+n;
}
public static void main(String[] args){
System.out.println(new digui().test(64));
}
}
请问这个程序不就是自己调用自己递归6次么，时间复杂度不应该是logn才对么，为什么是nlogn呢？？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90916同步于 2016/8/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请问递归时的时间复杂度到底该怎么计算？
johnson123
2016/8/28镜像同步17 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
这个当然是logn了...
【 在 johnson123 的大作中提到: 】
: [code=java]
: public class digui {
: public int test(int n){
: ...................
去看一下master theorem，记得算法导论里有。
形如T(n)=2T(n/2)+O(n)的递推式，才是O(n*logn)。
你这段代码，递推式是T(n)=T(n/2)+O(1)，所以是O(logn)。
【 在 johnson123 的大作中提到: 】
: [code=java]
: public class digui {
: public int test(int n){
: ...................
你再仔细看看...
【 在 fuxuemingzhu 的大作中提到: 】
: 一看就不是不是6次啊，递归效率比较慢不可能On的。应该是个二叉树，所以是nlogn
那个是时间复杂度...“+n”操作复杂度是O(n)么？
【 在 johnson123 的大作中提到: 】
: 我return的明明是test(n/2)+n啊,后面就是加n，不是加1啊
计算test（64）需要test(32)
计算32需要16
计算16需要8
...
计算2需要1
这不就是6次吗？
【 在 fuxuemingzhu 的大作中提到: 】
: 一看就不是不是6次啊，递归效率比较慢不可能On的。应该是个二叉树，所以是nlogn