通过绘制函数调用图来计算很简单。简单地为n的每个值添加函数调用，看看这个数字是如何增长的。

大O是O(Z^n)， Z是黄金比例，约为1.62。

当我们增加n时，列奥纳多数和斐波那契数都接近这个比率。

与其他大O问题不同，输入中没有可变性，算法和算法的实现都是明确定义的。

不需要一堆复杂的数学。简单地画出下面的函数调用，并将函数与数字匹配。

如果你熟悉黄金比例你就能认出来。

这个答案比公认的f(n) = 2^n的答案更正确。永远不会。它会趋于f(n) = golden_ratio^n。

2 (2 -> 1, 0)

4 (3 -> 2, 1) (2 -> 1, 0)

8 (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)


14 (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
            (2 -> 1, 0)

            (3 -> 2, 1) (2 -> 1, 0)

22 (6 -> 5, 4)
            (5 -> 4, 3) (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

                        (3 -> 2, 1) (2 -> 1, 0)

            (4 -> 3, 2) (3 -> 2, 1) (2 -> 1, 0)
                        (2 -> 1, 0)

只要问问自己，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)

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

它的下端以2^(n/2)为界，上端以2^n为界(如其他注释中所述)。这个递归实现的一个有趣的事实是它本身有一个紧密的Fib(n)渐近界。这些事实可以总结为:

T(n) = Ω(2^(n/2))  (lower bound)
T(n) = O(2^n)   (upper bound)
T(n) = Θ(Fib(n)) (tight bound)

如果你愿意，可以用它的封闭形式进一步简化紧边界。

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