如何解决T（N）= T（N-2）+ T（2）+ N递归树

Question

我想找到涉及复发的算法的复杂性：

T（N）= T（n-2）+ T（2）+ n

T（n）是解决大小为n的问题所需的时间。我想使用递归树，但我的问题是T（2），我们可以认为T（2）将由T（n-2）支配。

Answer 1

假设您从

T（N）= T（N - 2）+ T（2）+ N。

然后

T（N）=

T（N - 2）+ T（2）+ N =

T（N - 4）+ 2T（ 2）+ N +（N - 2）=

T（N - 6）+ 3T（2）+ N +（N - 2）+（N - 4）=

...

T（K）+ Θ（N）T（2）+ ∑ _{I = N，N - 2，...，K} [I]

其中k是一些常数。

在最后一个表达式，

T（2）是一个常数，所以Θ（N）T（2）= Θ（n）的。也

∑ _{I = N，N - 2，...，K} [I] = Θ（N ），因为它是一个等差级数。

总之，T（N）= Θ（N ）。