递归树与二叉树成本计算

Question

我有以下递归：

T(n) = T(n/3) + T(2n/3) + O(n)

树的高度是2的3/2。现在这个递归树不是一个完整的二叉树。它有较低的节点缺失。这对我来说是有意义的，但是我不明白下面的欧米茄符号是如何与树中所有叶子的成本相关的。

“.所有叶子的总成本是Theta (n^log3/2的2)，因为log3/2的2是一个严格大于1的常数，所以它是小ω(N lg N)。

有人能帮我理解一下Theta(n^log3/2 of 2)是如何变成small omega(n lg n)的吗？

Answer 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)中。