Fibonacci序列的计算复杂性

Question

Fibonacci序列的计算复杂性我理解大O表示法，但我不知道如何为许多函数计算它。特别是，我一直试图找出Fibonacci序列的简单版本的计算复杂性：int Fibonacci(int n) {     if (n <= 1)         return n;     else         return Fibonacci(n - 1) + Fibonacci(n - 2); }斐波纳契序列的计算复杂度是多少？它是如何计算的？

Answer 1

您可以对时间函数进行建模以进行计算。Fib(n)作为计算的时间之和Fib(n-1)加上计算时间Fib(n-2)加上把它们加在一起的时间(O(1))。这是假设重复评估相同的Fib(n)采取同样的时间-即没有回忆录是有用的。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

解决这个递归关系(例如，使用生成函数)，最终得到答案。

或者，您可以绘制递归树，它将具有深度。n并直观地计算出该函数是渐近的。O(2n)..然后你可以通过归纳来证明你的猜想。

基地：n = 1很明显

假设T(n-1) = O(2n-1), 因此

T(n) = T(n-1) + T(n-2) + O(1) 等于

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

然而，正如在评论中所指出的，这并不是严格的限制。关于这个函数的一个有趣的事实是，T(N)是渐近的。同作为.的价值Fib(n)因为两者都被定义为

f(n) = f(n-1) + f(n-2).

递归树的叶子将始终返回1。价值Fib(n)递归树中叶子返回的所有值之和，等于叶数。因为每片叶子都需要O(1)来计算，T(n)等于Fib(n) x O(1)..因此，这个函数的紧界是Fibonacci序列本身(~)θ(1.6n))。您可以像我前面提到的那样，通过使用生成函数来找出这种紧密的界限。

Answer 2

只需问自己需要执行多少个语句就可以了。F(n)完成。

为F(1)，答案是1(条件的第一部分)。

为F(n)，答案是F(n-1) + F(n-2).

那么满足这些规则的函数是什么呢？试一试ⁿ(a>1)：

aⁿ=a^(n-1)+a^(n-2)

除以.^(n-2):

a²=a+1

解为a你会得到(1+sqrt(5))/2 = 1.6180339887，也称为黄金比率.

所以它需要指数时间。