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

     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)

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

证明答案很好，但我总是不得不手工做一些迭代来真正说服自己。所以我在白板上画了一个小的调用树，并开始计算节点。我将计数分为总节点、叶节点和内部节点。以下是我得到的答案:

IN | OUT | TOT | LEAF | INT
 1 |   1 |   1 |   1  |   0
 2 |   1 |   1 |   1  |   0
 3 |   2 |   3 |   2  |   1
 4 |   3 |   5 |   3  |   2
 5 |   5 |   9 |   5  |   4
 6 |   8 |  15 |   8  |   7
 7 |  13 |  25 |  13  |  12
 8 |  21 |  41 |  21  |  20
 9 |  34 |  67 |  34  |  33
10 |  55 | 109 |  55  |  54

显而易见的是，叶节点的数量是fib(n)经过几次迭代才发现，内部节点的数量是fib(n) - 1。因此节点总数为2 * fib(n) - 1。

由于在对计算复杂度进行分类时去掉了系数，最终答案是θ(fib(n))。

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

     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)

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

在麻省理工学院有一个关于这个具体问题的很好的讨论。在第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个斐波那契数的封闭形式表达的讨论。