您能否檢查一下這個替換是否合適？

Question

問題：

使用resubstitution解決以下遞歸方程：

T（N）= 2T（N-1）+ N; N> = 2，T（1）= 1

到目前爲止，我有這樣的：

T（N）= 2T（N-1）+ N

= 2（2T第（n-2）+（N-1））+ N

= 4T（N-2）+ 3N -2

= 2（4T（N-3）+ 3（n-1個）-2）+ n

= 2（4T（N-3）+ 3N -3 -2）+ N

= 2（4T（N-3）+ 3N -5）+ N

= 8T（N-3- ）+ 6N - 10 + N

= 8T（N-3）+ 7N -10

我只是想知道，到目前爲止，我處理這個方法是正確的。 任何幫助表示讚賞，謝謝。

Answer 1

這一步是錯誤的：

= 4T(n-2) + 3n -2 

= 2(4T(n-3) + 3(n-1) -2) + n 

應該

= 4T(n-2) + 3n -2 

= 4(2T(n-3) + (n-2)) + 3n - 2 

您可以通過2T(n-i-1) + (n-i)更換T(n-i)。

除此之外，我認爲你錯了。你的老師要你做什麼，是感覺T(n)將會是什麼值。在這種情況下，您會發現每次迭代時，都會將第一個係數乘以2，最後得到an+b這樣的成員。這意味着T(n) = 2^n + O(n)因爲只有最大的成員很重要。