遞歸樹和二叉樹成本計算

我有以下遞歸：遞歸樹和二叉樹成本計算

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

遞歸樹和二叉樹成本計算

回答

相關問題