0 
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、理由を説明してください。

4

2 に答える 2

1

末尾nが関数呼び出しではないため、後者になります（前者にするためには、次のようにする必要がありますreturn(DAA(n/2)+DAA(n/2)+DAA(n-1));

于 2013-07-23T15:05:50.410 に答える
0

通常、任意の数の加算の計算は一定時間と見なされます。したがって

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

あれは

T(C) = 2T(N/2)+c
于 2013-07-23T15:08:36.820 に答える