1

私はこの漸化式を持っています

T(n) = T(n-1) + n, for n ≥ 2
T(1) = 1

演習：反復法を使用して漸化式を解き、漸近的な実行時間を与えます。

だから私はそれを次のように解決しました：

T(n) = T(n-1) + n 
        = T(n-2)  + (n - 1) + n 
        = T(n-3) + (n - 2) + (n - 1) + n 
        = … 
        = T(1) + 2 + … (n - 2) + (n - 1) + n **
        = 1 + 2 + … + (n - 2) + (n - 1) + n
        = O(n^2)

いくつか質問があります：

1）漸近的な実行時間を見つけるにはどうすればよいですか？

** 2）この問題の状態でT（1）は、nがあったことを意味します。これは、数値で減算すると、結果1になります。

3）T（0）= 1の場合、およびT（2）= 1の場合はどうなりますか？

編集：4）なぜn ≥ 2便利なのですか？

中期テストでは本当に理解する必要があります

4

1 に答える 1

2 
T(n) = T(n-1) + n, for n ≥ 2
T(1) = 1

実行時間を表す場合T(x)：

あなたはすでに漸近的な実行時間を見つけましたO(n^2)（二次）。

T(0) = 1関係がまたはに変更された場合T(2) = 1でも、実行時間は2次です。定数を追加したり、定数を掛けたりしても漸近的な振る舞いは変わりません。初期条件を変更すると、次の項に定数が追加されるだけです。

n ≥ 2は関係に存在するためT(n)、すべての正の値に対して一度に定義されnます。それ以外の場合は、両方の行がに適用されT(1)ます。T(1)をT(0)使用して計算することはできませんT(n) = T(n-1) + n。可能であったとしてもT(1)、2つの異なる（そして潜在的に一貫性のない）方法で定義されます。

于 2012-11-17T09:59:52.050 に答える