algorithm - 我如何展开复发:T(n)= 2T((n + 2)/3)

我正试图解决这一问题，但我不知道如何展开。

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

我能忽略这个“+2”并把它当作2t（n/3）+1来解决吗？
这来自一个使用V[a..b]数组的问题，并返回：

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

其中Y是(2a+b)/3 and Z is (a+2b)/3
所以：((b-a+3)/3) = ((n+2)/3)

最佳答案

某种程度上。这个技巧的严格版本是设置U(n) = T(n+1)并编写

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的渐近表达式。

关于algorithm - 我如何展开复发:T(n)= 2T((n + 2)/3)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42094506/