algorithm - 我怎样才能展开重复: T(n)=2T((n+2)/3)

Question

我正在尝试解决这个复发，但我不知道如何展开。

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，Z 是 (a+2b)/3

所以:((b-a+3)/3) = ((n+2)/3)

Answer 1

有点。这个技巧的严格版本是设置 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。