通过绘制函数调用图来计算很简单。简单地为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，也就是黄金比例。

所以需要指数级的时间。

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

在根上，你正在计算:

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-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)

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