time-complexity - 斐波那契数列的计算复杂度

Question

我理解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直在尝试计算斐波那契数列的简单版本的计算复杂性:

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(2 n ) 。然后你可以通过归纳法证明你的猜想。

基地:n = 1很明显

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

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

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

但是，正如评论中指出的，这不是严格限制。关于此函数的一个有趣事实是，T(n) 与 Fib(n) 的值渐近相同因为两者都定义为

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

递归树的叶子总是返回1。Fib(n)的值是递归树中叶子返回的所有值的总和，等于叶子的数量。由于每个叶子需要 O(1) 来计算，T(n)等于Fib(n) x O(1) 。因此，该函数的紧界是斐波那契数列本身(~ θ(1.6 n ) )。您可以通过使用我上面提到的生成函数来找出这个紧界。