寻找时间复杂

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

回答