斐波那契数列的计算复杂度

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

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

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

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

aⁿ == a^{(n - 1)} + a⁽²⁾

再除以a⁽²⁾:

a² == a + 1

求出a，就得到(1+sqrt(5))/2 = 1.6180339887，也就是黄金比例。

所以需要指数级的时间。

你对时间函数建模，以计算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)。然后你可以用归纳法证明你的猜想。

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

附:如果你想了解更多信息，在维基百科上有关于第n个斐波那契数的闭式表达式的讨论。

好吧，根据我的说法，它是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) ]的阶。

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

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

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

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

     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步骤，但也是指数级的。

成本函数定义为从输入大小到解决问题的步数。当你看到动态版本的斐波那契(n步骤计算表)或最简单的算法来知道一个数字是否是素数(sqrt (n)分析数字的有效除数)。你可能会认为这些算法是O (n)或O (sqrt (n))，但这根本不是真的，原因如下: 你的算法的输入是一个数字:n，使用二进制符号，整数n的输入大小是log2 (n)，然后做一个变量变化

m = log2(n) // your real input size

让我们找出作为输入大小的函数的步数

m = log2(n)
2^m = 2^log2(n) = n

那么你的算法的代价作为输入大小的函数是:

T(m) = n steps = 2^m steps

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

          n
(n-1)      (n-2)
(n-2)(n-3) (n-3)(n-4) ...so on

这里假设上面树的每一层都用i表示 因此,< / p >

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

通过绘制函数调用图来计算很简单。简单地为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)

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} and f_{n+2} = f_{n} + 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)

由于x_2的范数小于1，当n趋于无穷时，相应的项消失;因此，求出小于(x_1^n)/√(5)的最大整数就足以精确地找到答案。通过使用重复平方的技巧，这可以只使用O(log_2(n))乘法(和加法)操作来完成。内存的复杂性甚至更令人印象深刻，因为它可以以一种方式实现，您总是需要在内存中保存最多1个值小于答案的数字。然而，由于这个数字不是一个自然数，这里的内存复杂度取决于您是使用固定的位来表示每个数字(因此进行有错误的计算)(在这种情况下是O(1)内存复杂度)还是使用像图灵机这样更好的模型，在这种情况下，需要进行更多的分析。