好吧，根据我的说法，它是O(2^n)，因为在这个函数中，只有递归花费了相当多的时间(分治)。我们看到，上面的函数将在树中继续存在，直到叶子趋近于F(n-(n-1))级，即F(1)。因此，当我们在这里记下树的每个深度处遇到的时间复杂度时，求和级数为:

1+2+4+.......(n-1)
= 1((2^n)-1)/(2-1)
=2^n -1

它是2^n的O(2^n)阶。

它的下端以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个斐波那契数的封闭形式表达的讨论。

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

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)

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

在根上，你正在计算:

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

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