Fibonacci序列-时间复杂度

Question

给出了n>1的fib(n)=fib(n-1)+fib(n-2)，并给出了fib(0)=a，fib(1)=b ( a，b >0)，下面哪个是正确的？

fib(n) is 

Select one or more:
a. O(n^2)
b. O(2^n)
c. O((1-sqrt 5)/2)^n)
d. O(n)
e. Answer depends on a and b.
f. O((1+sqrt 5)/2)^n)

解决斐波纳契序列我知道：

fib(n)= 1/(sqrt 5) ((1+sqrt 5)/2)^n - 1/(sqrt 5) ((1-sqrt 5)/2)^n

但是，在这种情况下，时间的复杂性是什么呢？这是否意味着答案是c和f？

Answer 1

从公式的封闭形式来看，当1 / (sqrt 5) ((1 - sqrt 5) / 2)^n增长到无穷大(|(1 - sqrt 5) / 2| < 1)时，术语n限制了0。因此，我们可以忽略这一术语。此外，在时间复杂性理论中，我们不关心乘法常数，以下是正确的：

fib(n) =Θ(φ^n)

其中φ= (1 + sqrt 5) / 2 a.k.a.黄金比常数。

这是一个指数函数，我们可以排除a, d, e。我们可以排除c，因为有人说它限制了0。但是答案b也是正确的，因为φ < 2和O表示一个上限。

最后，正确的答案是：

b，f

Answer 2

a=1 and b=1或a=1 and b=2时，Θ(φ^n)是正确的。The value of φ depends on a and b。

对于计算fib(n-1)和fib(n-2)，如果递归计算它们的复杂度是exponential，但是如果我们保存最后两个值并使用它们，则复杂度是O(n)，而不是依赖于a和b。