我正在尝试解决这个复发问题,但我不知道如何展开它。
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)
Where Y
is (2a+b)/3 and Z is (a+2b)/3
So: ((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
(e.g., U(n) = O(n^log3(2))
)然后你应该能够找到一个渐近表达式T
相同的顺序。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)