在麻省理工学院有一个关于这个具体问题的很好的讨论。在第5页，他们指出，如果你假设一个加法需要一个计算单位，那么计算Fib(N)所需的时间与Fib(N)的结果密切相关。

因此，你可以直接跳到斐波那契数列的非常接近的近似:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

因此，假设朴素算法的最坏情况是

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS:如果你想了解更多信息，维基百科上有关于第n个斐波那契数的封闭形式表达的讨论。

通过绘制递归树可以更好地估计递归算法的时间复杂度，在这种情况下，绘制递归树的递归关系为T(n-1) =T(n- 2)+O(1) 注意，每一步花费O(1)意味着常数时间，因为它只做了一次比较来检查if块中的n值。递归树是这样的

          n
   (n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

这里假设上面树的每一层都用i表示 因此,

i
0                        n
1            (n-1)                 (n-2)
2        (n-2)    (n-3)      (n-3)     (n-4)
3   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)

假设在特定的i值处，树就结束了，也就是当n-i=1时，因此i=n-1，也就是说树的高度是n-1。 现在让我们看看树中n层中的每一层做了多少工作。注意，按照递归关系，每一步花费O(1)时间。

2^0=1                        n
2^1=2            (n-1)                 (n-2)
2^2=4        (n-2)    (n-3)      (n-3)     (n-4)
2^3=8   (n-3)(n-4) (n-4)(n-5) (n-4)(n-5) (n-5)(n-6)    ..so on
2^i for ith level

因为i=n-1是树的高度，所以每一层所做的功为

i work
1 2^1
2 2^2
3 2^3..so on

因此，所做的总功将是每一层所做的功的总和，因此它将是2^0+2^1+2^2+2^3…+2^(n-1)，因为i=n-1。 通过几何级数，这个和是2^n，因此总时间复杂度是O(2^n)

将计算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)。因此，这个函数的紧界是斐波那契数列本身(~θ(1.6n))。你可以使用我上面提到的生成函数来找到这个紧边界。

在麻省理工学院有一个关于这个具体问题的很好的讨论。在第5页，他们指出，如果你假设一个加法需要一个计算单位，那么计算Fib(N)所需的时间与Fib(N)的结果密切相关。

因此，你可以直接跳到斐波那契数列的非常接近的近似:

Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)

因此，假设朴素算法的最坏情况是

O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))

PS:如果你想了解更多信息，维基百科上有关于第n个斐波那契数的封闭形式表达的讨论。

由于计算的重复，朴素递归版本的斐波那契是指数型的:

在根上，你正在计算:

F(n)取决于F(n-1)和F(n-2)

F(n-1)又取决于F(n-2)和F(n-3)

F(n-2)又取决于F(n-3)和F(n-4)

然后你在每一个二级递归调用中都浪费了大量的数据，时间函数看起来像这样:

T（n） = T（n-1） + T（n-2） + C，C 常数

T（n-1） = T（n-2） + T（n-3） > T（n-2） 则

T（n） > 2*T（n-2）

...

T(n) > 2^(n/2) * T(1) = O(2^(n/2))

这只是一个下界，对于你的分析来说应该足够了，但实时函数是一个常数的因子，根据相同的斐波那契公式，封闭形式是已知的黄金比例的指数。

此外，你可以使用动态规划找到优化版的斐波那契函数，如下所示:

static int fib(int n)
{
    /* memory */
    int f[] = new int[n+1];
    int i;

    /* Init */
    f[0] = 0;
    f[1] = 1;

    /* Fill */
    for (i = 2; i <= n; i++)
    {
        f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

这是优化的，只做n步，但也是指数级的。

Cost functions are defined from Input size to the number of steps to solve the problem. When you see the dynamic version of Fibonacci (n steps to compute the table) or the easiest algorithm to know if a number is prime (sqrt(n) to analyze the valid divisors of the number). you may think that these algorithms are O(n) or O(sqrt(n)) but this is simply not true for the following reason: The input to your algorithm is a number: n, using the binary notation the input size for an integer n is log2(n) then doing a variable change of

m = log2(n) // your real input size

让我们找出作为输入大小的函数的步数

m = log2(n)
2^m = 2^log2(n) = n

那么你的算法的代价作为输入大小的函数是:

T(m) = n steps = 2^m steps

这就是为什么成本是指数级的。

No答案强调可能是计算序列的最快和最节省内存的方法。斐波那契数列有一个封闭形式的精确表达式。它可以通过生成函数或线性代数来求出来，就像我现在要做的。

令f_1,f_2，…为f_1 = f_2 = 1的斐波那契数列。现在考虑一个二维向量序列

f_1  ,  f_2  ,  f_3  ,  ...
f_2  ,  f_3  ,  f_4  ,  ...

观察向量序列中的下一个元素v_{n+1}是M.v_{n}，其中M是由给出的2x2矩阵

M = [0 1]
    [1 1]

由于f {n + 1} = f {n + 1}和f f {n} {n + 2} = + f {n + 1}

M可以对复数进行对角化(实际上也可以对实数进行对角化，但通常不是这样)。M有两个不同的特征向量

1      1
x_1    x_2

其中，x_1 =(1+根号(5))/2和x_2 =(1-根号(5))/2是多项式方程x*x-x-1 = 0的异解。对应的特征值是x_1和x_2。把M看成是一个线性变换然后改变基底，看它等价于

 D = [x_1  0]
     [0  x_2]

为了求出f_n，求出v_n，然后看第一个坐标。为了求v_n对v_1进行M n-1次运算。但是应用mn -1次很简单，只要把它看成d，然后利用线性就可以发现

f_n = 1/sqrt(5)*(x_1^n-x_2^n)

Since the norm of x_2 is smaller than 1, the corresponding term vanishes as n tends to infinity; therefore, obtaining the greatest integer smaller than (x_1^n)/sqrt(5) is enough to find the answer exactly. By making use of the trick of repeatedly squaring, this can be done using only O(log_2(n)) multiplication (and addition) operations. Memory complexity is even more impressive because it can be implemented in a way that you always need to hold at most 1 number in memory whose value is smaller than the answer. However, since this number is not a natural number, memory complexity here changes depending on whether if you use fixed bits to represent each number (hence do calculations with error)(O(1) memory complexity this case) or use a better model like Turing machines, in which case some more analysis is needed.