我有以下递归：
T(n) = T(n/3) + T(2n/3) + O(n)
这棵树的高度是二分之三的对数。现在这个递归的递归树不是一个完整的二叉树。它下面缺少节点这对我来说很有意义，但是我不明白下面的小欧米茄符号是如何与树上所有叶子的成本相关的。
“……所有叶子的总成本将是θ（n^log3/2/2/2/2/2），因为log3/2/2是严格大于1的常数，所以是小Ω（n lgn）。”
有人能帮助我理解
Theta(n^log3/2 of 2)是如何变成small omega(n lg n)的吗？ 最佳答案
好的，回答你关于为什么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)中
关于algorithm - 递归树和二叉树成本计算，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2768393/