小编And*_*laM的帖子

我在确定下一个函数的时间复杂度时遇到问题：

void fun(int n)
{
  console.log(n);
  for(int i=n;i>1;i--)
  {
    fun(i/2);
  }
}

观察它，我可以说递归树的最大高度是logn，从级别 1 到级别，每个级别logn都会有n-k调用，但我不知道如何使用这些信息。当我尝试写递推方程时，我得到如下结果：

T(n)=T(n/2)+T((n-1)/2)+T((n-2)/2)+...+T(1),

但我再次尝试简化它失败了。如何解决这个问题以便我知道什么是复杂性？