解决在使用迭代方法的递推关系 [英] Solving a recurrence relation using iteration method

问题描述

考虑这个例子：

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

我假定T（1）= 0

I assumed T(1) = 0

和试图解决它通过以下方式

and tried to solve it in the following way

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)               

但我不能来这方面有任何的结论。我很困惑，我该怎么做下一步。

but I could not come to any conclusion about this. I am confused about what should I do in the next step.

推荐答案

您的做法是合理的，但你会看到，如果你把它改写略有不同做什么：

Your approach is sound, but you'll see what to do if you rewrite it slightly differently:

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 趋于无穷大，看看会发生什么。这将有助于如果您熟悉几何级数。

Now, let k tend to infinity and see what happens. It would help if you're familiar with geometric series.

这篇关于解决在使用迭代方法的递推关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！