给定递归方程的时间复杂度

嗨，我可以知道对于给定的递归方程，T（N）= 2T（N/2）+ 2 什么是大哦时间复杂度，并且可以提供任何材料递归算法的精简时间复杂度。在此先感谢。给定递归方程的时间复杂度

2011-12-26 R45c4l

这是~~O(nlgn)~~编辑：O(n)因为+2术语显然属于主定理的第一种情况下，如Cormen的Introduction to Algorithms，章I.4.5描述。

2011-12-26 14:11:49 MagnatLU

我认为你错了，刚才我想通了，看看这个 http://en.wikipedia.org/wiki/Master_theorem#Application_to_common_algorithms 答案是O（n） – R45c4l 2011-12-26 16:41:36

我认为你是对的。毕竟那些年我忘记了大哦和theta之间的区别。我会解决我的答案。 – MagnatLU 2011-12-26 17:27:31

回答