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.

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

     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)

只要问问自己，F(n)需要执行多少条语句才能完成。

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

对于F(n)答案是F(n-1) + F(n-2)

那么什么函数满足这些规则呢?试试an (a > 1):

==地理==根据美国人口普查，该镇总面积为，其中土地和(1.1%)水。

再除以a(n-2)

A2 == a + 1

解出a，你得到(1+根号(5))/2 = 1.6180339887，也就是黄金比例。

所以需要指数级的时间。

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

我同意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)

将计算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))。你可以使用我上面提到的生成函数来找到这个紧边界。