T(n) = T(n/2) + T(n/4) + O(1)，T(n) 是多少？
如何解决这个递归问题：T(n) = T(n/2) + T(n/4) + O(1)
主方法似乎没有帮助，因为这是不是 T(n) = aT(n/b) + f(n) 的形式。我被困了很长一段时间。
How to solve this recurrence: T(n) = T(n/2) + T(n/4) + O(1)
It doesn't seem like Master Method will help, as this is not in the form of T(n) = aT(n/b) + f(n). And I got stuck for quite a while.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Akra Bazzi 是一种比 Master 方法更强大的方法。
由于“非递归”项是 O(1)，因此它相当于求解方程
1/2^p + 1/4^p = 1而你得到的答案将是
T(n) = Theta(n^p)我相信解决上述问题（
1/2^p中的二次方程）可以得到p = log_2 phi其中phi 是黄金比例。计算得出
T(n) = Theta(n^0.694...)Akra Bazzi is a much more powerful method than Master method.
Since the 'non-recursive' term is O(1), it amounts to solving the equation
1/2^p + 1/4^p = 1And the answer you get will be
T(n) = Theta(n^p)I believe solving the above (quadratic in
1/2^p) gives usp = log_2 phiwhere phi is the golden ratio.Computing that gives us
T(n) = Theta(n^0.694...)