我如何展开复发：T（n）= 2T（（n + 2）/ 3） [英] How can I unfold the recurrence: T(n)=2T((n+2)/3)

问题描述

我正在尝试解决这种重复现象，但我不知道如何实现。

I'm trying to solve this recurrence, but I don't know how to unfold it.

T(n)=2T((n+2)/3) + 1

我可以忽略 +2 并按2T（n / 3）+ 1的方式解决它？

Can I ignore that "+2" and solve it as it was 2T(n/3) + 1?

这来自a来自使用 V [a ..b] 数组并返回以下内容：

This comes from a from a problem that uses a V[a..b] array and makes this return:

return V(X) + f(V, a, Y) + f(V, Z, b)

其中 Y 是（2a + b）/ 3而Z是（a + 2b）/ 3

所以：（（b-a + 3）/ 3）=（（n + 2）/ 3）

推荐答案

排序。此技巧的严格版本是设置 U（n）= T（n + 1）并写入

Sort of. The rigorous version of this trick is to set U(n) = T(n+1) and write

U(n) = T(n+1)
     = 2T((n+1+2)/3) + 1
     = 2T(n/3 + 1) + 1
     = 2U(n/3) + 1.

然后求解 U （例如， U（n）= O（n ^ log3（2））），然后您应该能够找到相同顺序的 T 的渐近表达式。

Then solve for U (e.g., U(n) = O(n^log3(2))) and then you should be able to find an asymptotic expression for T of the same order.

这篇关于我如何展开复发：T（n）= 2T（（n + 2）/ 3）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！