algorithm - 您能检查一下目前这种替换是否正确吗？

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗Update the question所以堆栈溢出的值小于aa>。
问题是：
使用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
我只是想知道到目前为止，我接近这个的方式是否正确。
感谢您的帮助。

最佳答案

这一步错了：

= 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)因为只有最大的成员才重要。