斐波那契数列的计算复杂度 [英] Computational complexity of Fibonacci Sequence

问题描述

我了解Big-O表示法，但是我不知道如何为许多函数计算它.特别是，我一直在尝试找出Fibonacci序列的朴素版本的计算复杂性:

I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

斐波那契数列的计算复杂度是多少?如何计算?

What is the computational complexity of the Fibonacci sequence and how is it calculated?

推荐答案

您将时间函数建模为将Fib(n)计算为计算Fib(n-1)的时间总和加上计算Fib(n-2)的时间加上将它们相加的时间一起(O(1)).假设对同一Fib(n)的重复求值花费相同的时间-即不使用记忆.

You model the time function to calculate Fib(n) as sum of time to calculate Fib(n-1) plus the time to calculate Fib(n-2) plus the time to add them together (O(1)). This is assuming that repeated evaluations of the same Fib(n) take the same time - i.e. no memoization is use.

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

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

您解决了这种递归关系(例如，使用生成函数)，最后得到了答案.

You solve this recurrence relation (using generating functions, for instance) and you'll end up with the answer.

或者，您可以绘制具有深度n的递归树，并直观地确定此函数是渐近的O(2 n ).然后，您可以通过归纳证明您的猜想.

Alternatively, you can draw the recursion tree, which will have depth n and intuitively figure out that this function is asymptotically O(2n). You can then prove your conjecture by induction.

基础: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)的值相同，因为两者都定义为

However, as noted in a comment, this is not the tight bound. An interesting fact about this function is that the T(n) is asymptotically the same as the value of Fib(n) since both are defined as

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

递归树的叶子将始终返回1.Fib(n)的值是递归树中叶子返回的所有值的总和，其等于叶子的计数.由于每个叶子将采用O(1)进行计算，因此T(n)等于Fib(n) x O(1).因此，此功能的紧密界是斐波那契序列本身(〜θ(1.6 n )).您可以使用上面提到的生成函数来找出这种紧密联系.

The leaves of the recursion tree will always return 1. The value of Fib(n) is sum of all values returned by the leaves in the recursion tree which is equal to the count of leaves. Since each leaf will take O(1) to compute, T(n) is equal to Fib(n) x O(1). Consequently, the tight bound for this function is the Fibonacci sequence itself (~θ(1.6n)). You can find out this tight bound by using generating functions as I'd mentioned above.

这篇关于斐波那契数列的计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！