algorithm - 对该算法的复杂性感到困惑

Question

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

我对包含术语 n 的 return 语句感到困惑。是否会被计算为T(n)=2T(n/2)+n；或者T(n)=2T(n/2)+c，请解释为什么？

Answer 1

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