algorithm - 解决具有多个 T(n) 的递归关系

Question

T(n) = 1/2(T(n − 1) + T(n − 2)) + cn，其中 c > 0

我无法理解如何解决具有多个 T(n) 的递归问题。我做了很多练习，只用一个 T(n) 来解决递归问题，并遵循我可以很好地完成的定义。但这不是可以用 Master 定理直接解决的递归。无论如何，我可以开始一个很好的方法来解决这个问题吗？

Answer 1

解决齐次递归:

T_H(n) = 1/2(T_H(n − 1) + T_H(n − 2))
r^2 - r/2 - 1/2 = 0
r = 1 or r = -1/2
T_H(n) = alpha * 1^n + beta * (-1/2)^n (alpha and beta to be determined by initial conditions)

求解特解

(1) 我们想找到一个 s(n) 使得 s(n) = 1/2(s(n-1)+s(n-2)) + cn

我们知道 cn 是一个多项式(在 n 中)，所以特殊的解也可以作为多项式找到。

尝试 s(n) = an 导致:an = 1/2(an-1 + an-2) + cn 和 an 中的所有项都简化了自己，所以尝试下一个程度:s(n) =an^2 + bn

an^2 + bn = 1/2 (a(n-1)^2 + b(n-1) + a(n-2)^2 + b(n-2) ) + cn

发展每个人然后确定我们得到

a = c/3
b = 5c/9

快速检查一下我们是否不相信自己进行有效微积分的能力:由于 s(n) 必须对所有 n 有效，让我们任意放置 n=2, c=7 并检查 s(2) 是否仍然验证 (1) 同上

n = 2, c=7
s(n)-1/2(s(n-1)+s(n-2))-cn ?= 0

下面的 Octave 显示确实 s(2) = 0

octave:1> n=2
n =  2
octave:2> c=7
c =  7
octave:3> c/3*n^2 + 5*c/9*n - 1/2*(c/3*(n-1)^2 + 5*c/9*(n-1) +c/3*(n-2)^2 + 5*c/9*(n-2))-c*n
ans = 0

复杂度

T(n) = T_H(n) + sp(n) = alpha + beta (-1/2)^n + c/3n^2 + 5c/9n

所以 T(n) 是 O(n^2)