algorithm - 这种算法的复杂性困惑

DAA(n)
{
    if(n<=1)
    {
         return 1;
    }
    else
    {
        return(DAA(n/2)+DAA(n/2)+n);
    }
}

我在含有n项的报表中感到困惑。它将被计算为T(n)=2T(n/2)+n；还是T(n)=2T(n/2)+c，请解释原因？

最佳答案

它将是后者，因为后面的n不在函数调用中（为了使它是前者，它需要类似于return(DAA(n/2)+DAA(n/2)+DAA(n-1));

关于algorithm - 这种算法的复杂性困惑，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17813907/