到目前为止，您能检查一下这种替换是否正确吗？

Question

问题是： 使用重新替换来求解以下递推方程： 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

您将T(n-i)替换为2T(n-i-1) + (n-i)。

除此之外，我认为你搞错了。你的老师想让你做的，是感受T(n)的价值。在本例中，您看到每次迭代时，第一个系数乘以2，最后有一个像an+b这样的成员。这意味着T(n) = 2^n + O(n)因为只有最大的成员才重要。