如何求解递推方程T(n)=T(n/2)+T(n/4)+\Theta(n)？
如何求解递推方程
1.T(n)=T(n/2)+T(n/4)+\Theta(n)
2.T(1)=1
使用 Big-Theta 表示法给出结果
How to solve the recurrence equation
1.T(n)=T(n/2)+T(n/4)+\Theta(n)
2.T(1)=1
Use Big-Theta notation to give the result
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
那么我们看一下carfuley这个问题我们就可以分析一下。
让我们从示例开始，当我们探索它们时，我们可以更好地理解如何解决它们（另一个问题是如何表示我们拥有的数据，但这是计算机知道如何表示可读的数据）。
（提示，任何低于 1 的值都会舍入为 1
T(1) = 1
T(2) = 1 + 1
T(3) = T(1.5) + 1
T(4) = T(2) + 1
T(5) = T(2.5) + T(1.25)
T(2.5) = T(1.25) + 1
T(6) = T(3) + T(1.3333)
现在，如果我们进行循环，我们就可以理解 1 和2 可以取 2 的上限或 1 的下界。
作为提示，如果你证明，当你取所有上限并得到你想要的 teta 时，如果你取你想要的所有下界 teta，那么你证明 现在让我们检查上面
的 teta
T(1) = 1
T(2) = 1 + 1
T(3) = T(2) + 1 = (1 + 1) +1
T(4) ) = T(2) + 1 = (1 + 1) +1
T(5) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)
T(6) = T (3) + T(2) = (1 + 1 + 1) + (1 + 1)
你能看出它是线性的吗？
你能从中得出一个公式吗？
。
祝你好运 ，
不要忘记下界分析。
well then we look at this question carfuley we can analys it.
lets start with examples, as we explore them we could reach better understanding on how to solve them(the other problem is how to represent the data we have, but that is a computer sientenst to know how to represent data to be readable).
(hint, anything below 1 is rounder to 1
T(1) = 1
T(2) = 1 + 1
T(3) = T(1.5) + 1
T(4) = T(2) + 1
T(5) = T(2.5) + T(1.25)
T(2.5) = T(1.25) + 1
T(6) = T(3) + T(1.3333)
now if we do rounds we can get to understanding that whats betwee 1 and 2 can take upper bound of 2 or lower bound of 1.
as a hint ill say if you prove that when you take all upper bounds and get the teta you want, and if you take all the lower bound teta you want, then you prove that its bounded by the same teta.
now lets examine the upper teta
T(1) = 1
T(2) = 1 + 1
T(3) = T(2) + 1 = (1 + 1) +1
T(4) = T(2) + 1 = (1 + 1) +1
T(5) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)
T(6) = T(3) + T(2) = (1 + 1 + 1) + (1 + 1)
do you see its linear?
can you come out of a furmula from this?
this is how you approach this kind of questions.
good luck,
don't forget the lower bound analysis.
我不想给你直接的答案，但我的提示：寻找形式的数学级数：
I don't want to give you direct answer, but my hint: look for Mathematical series of form: