递归关系家庭作业的挣扎

Question

下面是问题：

在给定T(1) =θ(1)的情况下，通过获得T(n)的θ界限来求解递归。

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