斐波那契数列 - 时间复杂度
Fibonacci Sequence - Time Complexity
假设 n>1 时 fib(n)=fib(n-1)+fib(n-2) 并且假设 fib(0)=a, fib(1)=b (some 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？
从公式的封闭形式来看，1 / (sqrt 5) ((1 - sqrt 5) / 2)^n 项有极限 0，因为 n 增长到无穷大 (|(1 - sqrt 5) / 2| < 1)。因此我们可以忽略这个词。此外，由于在时间复杂度理论中我们不关心乘法常数，因此以下内容为真：
fib(n) = Θ(φ^n)
其中 φ = (1 + sqrt 5) / 2 a.k.a。 golden ratio constant.
所以它是一个指数函数，我们可以排除 a, d, e。我们可以排除 c，因为正如所说它有限制 0。但答案 b 也是正确的，因为 φ < 2 和 O 表示上限。
最后正确答案是：
b, f
Θ(φ^n) 在 a=1 and b=1 或 a=1 and b=2 时是正确的。 The value of φ depends on a and b.
对于计算 fib(n-1) 和 fib(n-2)，如果我们递归计算它们，复杂度为 exponential，但如果我们保存最后两个值并使用它们，复杂度为 O(n) 而不是取决于 a 和 b。
假设 n>1 时 fib(n)=fib(n-1)+fib(n-2) 并且假设 fib(0)=a, fib(1)=b (some 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？
从公式的封闭形式来看，1 / (sqrt 5) ((1 - sqrt 5) / 2)^n 项有极限 0，因为 n 增长到无穷大 (|(1 - sqrt 5) / 2| < 1)。因此我们可以忽略这个词。此外，由于在时间复杂度理论中我们不关心乘法常数，因此以下内容为真：
fib(n) = Θ(φ^n)
其中 φ = (1 + sqrt 5) / 2 a.k.a。 golden ratio constant.
所以它是一个指数函数，我们可以排除 a, d, e。我们可以排除 c，因为正如所说它有限制 0。但答案 b 也是正确的，因为 φ < 2 和 O 表示上限。
最后正确答案是：
b, f
Θ(φ^n) 在 a=1 and b=1 或 a=1 and b=2 时是正确的。 The value of φ depends on a and b.
对于计算 fib(n-1) 和 fib(n-2)，如果我们递归计算它们，复杂度为 exponential，但如果我们保存最后两个值并使用它们，复杂度为 O(n) 而不是取决于 a 和 b。