如何计算大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

回答