斐波那契数列的计算复杂度
我了解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直试图弄清楚斐波那契数列的原始版本的计算复杂性：
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波那契数列的计算复杂度是多少，它是如何计算的？
您将计算 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))。您可以通过使用我上面提到的生成函数来找出这个紧密的界限。
只需问问自己需要执行多少语句才能完成 F(n)。
对于 F(1)，答案是 1（条件的第一部分）。
对于 F(n)，答案是 F(n-1) + F(n-2)。
那么什么函数满足这些规则呢？尝试 (a > 1)：
一个 == a(n-1) + a(n-2)
除以 a(n-2)：
a2 == a + 1
求解 a 得到 (1+sqrt(5))/2 = 1.6180339887，也称为 golden ratio。
所以它需要指数级的时间。
x^n。因此x^n = x^n-1 + x^n-2。
我同意 pgaur 和 rickerbh 的观点，递归斐波那契的复杂度是 O(2^n)。
我通过一个相当简单的结论得出了同样的结论，但我相信仍然是有效的推理。
首先，这一切都是为了弄清楚在计算第 N 个斐波那契数时调用了多少次递归斐波那契函数（从现在开始为 F() ）。如果它在序列 0 到 n 中的每个数字被调用一次，那么我们有 O(n)，如果它被每个数字调用 n 次，那么我们得到 O(n*n) 或 O(n^2)，等等。
因此，当为数字 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 时调用 F() 的总次数为 2x32=64=2^6。
现在，就复杂性而言：
O( F(6) ) = O(2^6)
O( F(n) ) = O(2^n)
关于这个 specific problem over at MIT 的讨论非常好。在第 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：如果您想了解更多信息，可以在 Wikipedia 上讨论 closed form expression of the Nth Fibonacci number。
您可以扩展它并进行可视化
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-1)的？
T(n-1) > T(n-2) 所以我可以更改 T(n-2) 并放入 T(n-1)。我只会得到一个对 T(n-1) + T(n-2) 仍然有效的上限
通过绘制递归树可以更好地估计递归算法的时间复杂度，在这种情况下，绘制递归树的递归关系为 T(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 的特定值处，树结束，这种情况将是当 ni=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)
证明答案很好，但我总是必须手动进行几次迭代才能真正说服自己。所以我在白板上画了一个小的调用树，开始计算节点。我将计数分为总节点、叶节点和内部节点。这是我得到的：
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))。
1 添加到单个累加器 Fib(n) 次，有趣的是它仍然是 θ(Fib(n))。
0：递归基本情况是 0 和 1，因为它们会添加 Fib(n-1) + Fib(n-2)。因此，对于节点总数，来自 this link-only answer 的 3 * Fib(n) - 2 可能更准确，而不是 2 * Fib(n) - 1。
它的下端以 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)
如果您愿意，可以使用它的 closed form 进一步减少紧密限制。
通过绘制函数调用图很容易计算。只需为每个 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)
好吧，据我说是 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) ] 的顺序。
由于计算中的重复，斐波那契的朴素递归版本在设计上是指数的：
从根本上讲，您正在计算：
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)
那么您在每个级别 2 递归调用都在计算中浪费了大量数据，时间函数将如下所示：
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))
这只是一个下限，就您的分析而言应该足够了，但实时函数是相同斐波那契公式的常数因子，并且已知 closed form 是黄金比例的指数。
此外，您可以使用如下动态编程找到优化的斐波那契版本：
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 步，但也是指数级的。
成本函数定义为从输入大小到解决问题的步骤数。当您看到 Fibonacci 的动态版本（计算表格的 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
这就是成本呈指数增长的原因。
没有答案强调可能是计算序列的最快和最节省内存的方法。斐波那契数列有一个封闭形式的精确表达式。它可以通过使用生成函数或使用线性代数来找到，就像我现在要做的那样。
令 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+sqrt(5))/2 和 x_2 = (1-sqrt(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 次。但是应用 M n-1 次很容易，只要将其视为 D。然后使用线性可以找到
f_n = 1/sqrt(5)*(x_1^n-x_2^n)
由于 x_2 的范数小于 1，对应的项随着 n 趋于无穷大而消失；因此，获得小于 (x_1^n)/sqrt(5) 的最大整数就足以准确地找到答案。通过利用重复平方的技巧，这可以仅使用 O(log_2(n)) 乘法（和加法）操作来完成。内存复杂性更令人印象深刻，因为它可以以一种方式实现，即您始终需要在内存中最多保存 1 个值小于答案的数字。但是，由于这个数字不是自然数，这里的内存复杂度会根据您是否使用固定位来表示每个数字（因此进行错误计算）（在这种情况下为 O(1) 内存复杂度）或使用更好的模型（如图灵机，在这种情况下需要更多的分析。
