如何計算大O符號遞歸算法的複雜性？

遞歸算法具有複雜： W（N）= 2W（N/2）+Θ（n）的如何計算大O符號遞歸算法的複雜性？

我的解決辦法或猜測爲O（n）。

如何解決這種複雜性？

2015-10-17 J.Olufsen

再做一次猜測，它不止於此。請參閱https://en.wikipedia.org/wiki/Master_theorem – Henry

它是否具有複雜性？ –

是的，它的n日誌n – Henry

這種情況由Master Theorem覆蓋。這也很容易直接看到：

W(n) = 2 W(n/2) + Theta(n) 
    = 2(2 W(n/4) + Theta(n/2)) + Theta(n) 
    = 4 W(n/4) + 2 Theta(n)

所以每個遞歸步驟，你得到另一個西塔（n）和遞歸的深度爲log N。總的努力因此是O（n log n）。

2015-10-17 09:00:46 Henry

回答