循环中递归调用的递归函数的时间复杂度

Question

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

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),

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

Answer 1

好的，您正确地确定了树的深度和节点数，并且正确地编写了循环方程，但是让我们采用不同的方法，看看我们是否可以注意到任何模式，以便我们可以进一步简化方程。

对于 n=1，复杂度将是常数 c，可以说：

T(1)=1
T(2)=T(1)+1
T(3)=T(1)+T(1)+1=T(2)+T(1)
T(4)=T(2)+T(1)+T(1)+1=T(3)+T(2)
T(5)=T(2)+T(2)+T(1)+T(1)+1=T(4)+T(2)
T(6)=T(3)+T(2)+T(2)+T(1)+T(1)+1=T(5)+T(3)
...

现在我注意到模式，该方程可以写为：

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

现在，要估计复杂性可能会很棘手，而且我无法给您答案，因为我相信这是 100% 真实的。但就我个人而言，由于方程中的第一个因素比第二个因素更强，我认为时间复杂度至少为O(n)。