尋找時間複雜

T（n）的時間複雜度= 1如果n < = 0 T（N）= T（N-1）+ T（ n-2）+ n

2010-09-24 sudh

你的基本情況是什麼？ n <= 0？ – AlcubierreDrive 2010-09-24 22:34:23

零接受答案和零upvotes？沒有辦法 – 2010-09-24 22:38:02

根據OEIS，該函數的閉合公式爲，表示該函數的漸近複雜度爲 alt text 。

2010-09-25 12:12:47 svick

考慮

F(n) = T(n) + n + 3.

這給了我們

F(n) - (n+3) = F(n-1) - (n-1+3) + F(n-2) - (n-2+3) + n 

i.e 

F(n) - 3 = F(n-1) - 2 + F(n-2) - 1 

i.e 

F(n) = F(n-1) + F(n-2)

這就好比序列的斐波那契！

衆所周知，對於斐波那契序列，F(n) = Theta(phi^n)其中phi是黃金比例。

2010-09-25 22:46:42

我同意這個結論，但我認爲證明是錯誤的：「ie」部分是不正確的。 – svick 2010-09-26 13:33:48

@Svick：這是基礎算術！我沒有說這是斐波那契序列。條款是不同的。 – 2010-09-26 13:40:01

@Moron：是的，它是基本的算術，但是（n + 1）！=（n-1）'，你不能忽略它。 – svick 2010-09-26 14:47:39

回答