math - 漸化式：T（n-1）のBigOを解く

Question

BigOの漸化式の問題をいくつか解決しています。

T(n) = T(n-1)

私は始めました：

T(n)   = T(n-1)
T(n-1) = T(n-2)
..
T(n) = T(n-k)

ここで、kをn-1に設定します

T(n) = T(1)

したがって、結果は次のようになります。

T(n) = O(1)

これが正しいかどうかは完全にはわかりませんが、これがとても簡単かどうかはわかりません。

Answer 1

基本ケースがある限り、そうです、それは正しいです。

再発は次のように定義されていると思います

T（0）= k（定数kの場合）、および

T（n + 1）= T（n）

次に、帰納法によって、すべての自然数nに対してT（n）=kであることを証明できます。

• 基本ケース：n = 0の場合、必要に応じてT（n）= T（0）=k。
• 帰納的ステップ： T（n）=kと仮定します。次に、必要に応じて、T（n + 1）= T（n）=kです。

したがって、T（n）= k = O（1）です。

お役に立てれば！