これらの2つの関数の漸近時間の複雑さはどのようになりますか？

Question

次の2つの機能を参照してください。

A(n) 
    { if(n<=1) 
      return; 
     else 
      return(A(n/4)+A(n/4)+A(n/4)); 
    } 

とワン

 A(n) 
    { if(n<=1) 
      return; 
     else 
      return(3*A(n/4)); 
    } 

秒、私の説明と機能の両方のための方程式を伝え、その後、漸近的にそれをバインドしてください。

実際には、なぜ私はこの質問をしていますが、私は式

T（N）= 3T（N/4）+1

を得たので、私は（最初のケースを想定マスターズ、ツリー方式を用いています）とgot- THETA（n^0.79）

しかし、私はこの式が第2のケースであるとは思いませんか？一つのことは、両方のケースで複雑さが違うということです。両方の場合で再帰呼び出しの数が異なります。

ご理解ください。

Answer 1

あなたが最初のアルゴリズムの時間のための再帰は、

（n）はT = 3 Tであることを、あなたの主張では絶対に正しいです（N/4）+ O（1）を。

また、第1アルゴリズムと第2アルゴリズムが常に同じものを返すのも事実です。

ただし、ここで類似点は終了します。第2のアルゴリズムは、より巧みに構成されています。

return(A(n/4)+A(n/4)+A(n/4)); 

が

return(3*A(n/4)); 

と同じ値を返し、後者は単一の再帰呼び出しを行いながら、すなわち、です。時間のためにその再帰は、従って= T

T（n）が（N/4）+ O（1）ここ

（最後O（1）も乗算のコストを含みます戻り値は3で、これは複雑さとは関係ありません）