递归关系家庭作业的挣扎
问题如下：
给定 T(1) = theta(1)，通过获取 T(n) 的 theta 界来求解递推式。
T(n) = n + T(n-3)
尝试的解决方案：
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
当我仔细检查该解决方案是否适合递归时，它不起作用。
Here's the question:
Solve the recurrence by obtaining a theta bound for T(n) given that T(1) = theta(1).
T(n) = n + T(n-3)
Attempted Solution:
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
When I double check to see if the solution fits the recurrence, it doesn't work.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
问题是你得到了错误的求和。
它不是从 0 开始，因为您的最后一个 T 函数是 T(n - (n-1)) ，这意味着前一个函数是 T(n-(n-4)) 。所以求和从 4 开始，一直到 n。
如果你不知道如何求和，我建议你看一下求和公式的一些证明。这就是解决方案的样子。
The issue was that you were getting the wrong summation.
It doesn't start at 0, since your last T function was T(n - (n-1)) , which means previous one was T(n-(n-4)). So the summation starts at 4, and goes up till n.
If you don't know how to find the summation of this, I'd suggest you look at some of the proofs from the summation formula. This is what the solution looks like.