递归树和二叉树成本计算
我有以下递归：
T(n) = T(n/3) + T(2n/3) + O(n)
树的高度将为 2 的 log3/2。现在，此递归的递归树不是完整的二叉树。它的下部缺少节点。这对我来说很有意义，但是我不明白以下小欧米茄符号与树中所有叶子的成本有何关系。
“...所有叶子的总成本将为 Theta (n^log3/2 of 2)，由于 2 的 log3/2 是严格大于 1 的常数，因此它是小 omega(n lg n)。”
有人可以帮我理解Theta(n^log3/2 of 2)如何变成小omega(n lg n)吗？
I've got the following recursion:
T(n) = T(n/3) + T(2n/3) + O(n)
The height of the tree would be log3/2 of 2. Now the recursion tree for this recurrence is not a complete binary tree. It has missing nodes lower down. This makes sense to me, however I don't understand how the following small omega notation relates to the cost of all leaves in the tree.
"... the total cost of all leaves would then be Theta (n^log3/2 of 2) which, since log3/2 of 2 is a constant strictly greater then 1, is small omega(n lg n)."
Can someone please help me understand how the Theta(n^log3/2 of 2) becomes small omega(n lg n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
好的，回答您关于为什么
n^(log_1.5(2))是omega(n lg n)的明确问题：对于所有k> 1、n^k 的增长速度快于
n lg n。 （力量最终比原木增长得更快）。因此，由于2> 1.5，log_1.5(2)> 1，因此n^(log_1.5(2))的增长速度比n lg n更快。由于我们的函数位于Theta(n^(log_1.5(2)))中，因此它也必须位于omega(n lg n)中OK, to answer your explicit question about why
n^(log_1.5(2))isomega(n lg n):For all k > 1, n^k grows faster than
n lg n. (Powers grow faster than logs eventually). Therefore since2 > 1.5,log_1.5(2) > 1, and thusn^(log_1.5(2))grows faster thann lg n. And since our function is inTheta(n^(log_1.5(2))), it must also be inomega(n lg n)