递归树和二叉树成本计算

我有以下递归：递归树和二叉树成本计算

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

树的高度将LOG3 2/2。现在这种复发递归树不是完全二叉树树。它有下降的缺失节点。这对我来说很有意义，但我不明白以下小欧米茄符号如何与树中所有树叶的成本相关。

” ......中的所有叶的总成本将被西塔（N^log3中/ 2 2），因为2 log3中/ 2是常数严格大于1，较小的ω（ n lg n）“。

是否有人可以帮助我了解如何Theta(n^log3/2 of 2)成为small omega(n lg n)？

来源

2010-05-04 Tony The Lion

这对任何人都没有意义，除非你能向我们展示Theta和小欧米茄的功能。 – Puppy 2010-05-04 19:39:13

OK，回答你为什么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)

来源

2010-05-04 19:42:37 Yuliy

递归树和二叉树成本计算

回答

相关问题