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

发布于 2024-08-18 00:54:22 字数 324 浏览 8 评论 0 原文

考虑这个例子：

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)

，但我无法得出任何结论。我很困惑下一步应该做什么。

原文

Consider this example :

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

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

掩于岁月 2024-08-25 00:54:22

您的方法是合理的，但是如果您稍微不同地重写它，您就会看到该怎么做：

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

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

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