recurrence - 复发关系家庭作业斗争

Question

问题是：
在 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

当我仔细检查解决方案是否适合重复时，它不起作用。

Answer 1

问题是你得到了错误的总和。它不是从 0 开始的，因为您的最后一个 T 函数是 T(n - (n-1)) ，这意味着前一个是 T(n-(n-4))。所以总和从 4 开始，一直上升到 n。

如果你不知道如何求和，我建议你看看求和公式中的一些证明。这就是解决方案的样子。

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

= T(n-6) + (n-3) + n  

= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]

= T(1) + [4 + 7 + ... + n]

= theta(1) + (4 + n) * (n - 1)/6