求一个算法的复杂度，谢谢

xdshting

有如下递归函数f(n)，其时间复杂度为？
int f(int n){
  int sum = 0;
  for(int i=0; i <n; i++)
    sum = sum + i;
  return f(n/2) + f((n+1)/2) + sum;
}

wkq5325

递归？退出条件，。。。咋没有

zzyong08

回复 1# xdshting


复杂度 nlog(n)，每次递归是O(n)，大概递归log(n)次，所以是nlog(n)。

不过，如二楼所说，为啥没有退出条件。

xdshting

回复  xdshting


复杂度 nlog(n)，每次递归是O(n)，大概递归log(n)次，所以是nlog(n)。

不过，如二 ...
zzyong08 发表于 2010-09-13 09:14

    不好意思，这是我从别人网站上考过来的，google的面试题目
至于没有结束条件，我没注意，汗
我只是在想 f(n)=n+f(n/2)+f((n+1)/2)的时间复杂度的计算问题