再帰次のコードのビッグ-Oになりますどのような複雑

int f(int n) 
{ 
int i, x; 
if (n < 0) 

return 1; 
x = 0; 
for (i = 0; i < n; ++i) 

x = x + i; 
return x + f(n - 2); 
}

が、私はマスターの定理は、後者を使用する標準的なT（n）の形でそれを記述する方法を疑問に思います。 T（n）= n/2T（n-2）のようになりますか？

2012-02-29 Dmitry

この宿題はありますか？もしそうなら、 '宿題 'タグを使用してください。 –

いいえ、そうではありません、私はBig-O表記を理解しようとしており、このコードの複雑さがわかりません。 – Dmitry

-1

が関数の内部でそこにあるものを気にしないでください。この期間に依存して簡単にするために、あなたは、T（N）= nTの（N-2）にそれを近似することができます再帰呼び出しを参照してください...

サイズnの問題は、現在サイズn/2の問題になっています。

今、この再帰関数は何回呼び出されていますか？関数内のforループがn回実行されるため、n回実行されます。

したがって、T（n）= n * T（n/2）。

2012-06-13 06:27:22 phoenyx

フォームは正確にはT（n）=（n + 2）T（n-2）です。

しかしビッグ-Oは、単に最初の、唯一の

2012-02-29 04:00:10 nightf0x

なぜ（n + 2）、説明できますか？そしてBig-Oは何ですか？ – Dmitry

追加の2つの代入でループをn回反復処理しています – nightf0x

答えて