遞推關係：解決T（N-1）

Question

我爲解決大圓滿

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 = 0（1）。

希望這會有所幫助！