如何解決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 ）。