使用迭代方法求解递归关系

Question

考虑这个例子:

T(n) = T(7n/8) + 2n 

我假设T(1)= 0

并尝试以下列方式解决它

T(n) = T(7n/8) + 2n
     = T(49n/64) + 2.(7n/8) + 2n
     = T(343n/512) + 2.(7n/8).(7n/8)+ 2.(7n/8) + 2n 
     = T(1) + 2n ( (7n/8)^i + ..... + 1)               

但我无法得出任何结论.我对下一步该怎么办感到困惑.

Answer 1

你的方法是合理的,但如果你稍微改写它,你会看到该怎么做:

T(n) = T((7/8)^1 * n) + 2 * (7/8)^0 * n
     = T((7/8)^2 * n) + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     = T((7/8)^3 * n) + 2 * (7/8)^2 * n + 2 * (7/8)^1 * n + 2 * (7/8)^0 * n
     .
     .
     .
     = T((7/8)^k * n) + 2 * n * sum j = 0 to k-1 (7/8)^j

现在,让我们k倾向于无限,看看会发生什么.如果您熟悉几何系列会有所帮助.