本文介绍了我如何展开复发: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)
发布评论