algorithm - 该算法的复杂性混乱

Question

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，请解释为什么？

score 1 · Accepted Answer

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

score 0 · Accepted Answer

计算任何数的加法通常被认为是常数时间。所以

T(n) = 2T(N/2) + 2*time_to_compute_a_addition

那是

T(C) = 2T(N/2)+c

2 回答 2