通过绘制递归树可以更好地估计递归算法的时间复杂度，在这种情况下，绘制递归树的递归关系为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)

通过绘制递归树可以更好地估计递归算法的时间复杂度，在这种情况下，绘制递归树的递归关系为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)

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

在根上，你正在计算:

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

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

你可以展开它，有一个可视化

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

     = 2*T(n-1)   
     = 2*2*T(n-2)
     = 2*2*2*T(n-3)
     ....
     = 2^i*T(n-i)
     ...
     ==> O(2^n)

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.

我同意pgaur和rickerbh的观点，递归-fibonacci的复杂度是O(2^n)。

我通过一个相当简单但我相信仍然有效的推理得出了同样的结论。

首先，这完全是关于计算第n个斐波那契数时调用多少次递归斐波那契函数(F()从现在开始)。如果它在0到n的数列中被调用一次，那么我们有O(n)，如果它对每个数字被调用n次，那么我们得到O(n*n)或O(n²)，以此类推。

因此，当对一个数字n调用F()时，对一个给定的0到n-1之间的数字调用F()的次数随着趋近于0而增加。

作为第一印象，在我看来，如果我们把它放在视觉上，每次绘制一个单位F()被调用为给定的数字，我们会得到一种金字塔形状(也就是说，如果我们将单位水平居中)。就像这样:

n              *
n-1            **
n-2           ****  
...
2           ***********
1       ******************
0    ***************************

现在的问题是，随着n的增长，金字塔的底部扩大的有多快?

让我们举一个真实的例子，比如F(6)

F(6)                 *  <-- only once
F(5)                 *  <-- only once too
F(4)                 ** 
F(3)                ****
F(2)              ********
F(1)          ****************           <-- 16
F(0)  ********************************    <-- 32

我们看到F(0)被调用了32次，也就是2^5，在这个例子中是2^(n-1)

现在，我们想知道F(x)被调用了多少次，我们可以看到F(0)被调用的次数只是其中的一部分。

如果我们在心里把F(6)到F(2)线的所有*移到F(1)线中，我们看到F(1)和F(0)线现在长度相等。这意味着，当n=6 = 2x32=64=2^6时，total乘以F()被调用。

现在，说到复杂性:

O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)