我了解 Big-O 表示法，但我不知道如何为许多函数计算它。特别是，我一直试图弄清楚斐波那契数列的原始版本的计算复杂性：
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波那契数列的计算复杂度是多少，它是如何计算的？
Princess
问问题
373030 次
12 回答
408
您将要计算的时间函数建模为要计算的时间加上要计算的时间加上将它们加在一起的时间的总和 ( 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)
于 2008-12-11T20:29:12.750 回答
155
问问自己需要执行多少条语句F(n)才能完成。
对于F(1)，答案是1（条件的第一部分）。
对于F(n)，答案是F(n-1) + F(n-2)。
那么什么函数满足这些规则呢？尝试一个n (a > 1)：
a n == a (n-1) + a (n-2)
除以(n-2)：
一个2 == 一个 + 1
解决就a得到(1+sqrt(5))/2 = 1.6180339887，也就是所谓的黄金比例。
所以它需要指数级的时间。
于 2008-12-11T20:26:21.553 回答
37
我同意 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)
于 2014-04-15T21:38:56.573 回答
35
麻省理工学院对这个特定问题进行了很好的讨论。在第 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上讨论Nth Fibonacci 数的封闭形式表达式。
于 2008-12-11T21:10:03.057 回答
21
您可以扩展它并进行可视化
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)
于 2017-08-10T15:39:12.740 回答
20
通过绘制递归树可以更好地估计递归算法的时间复杂度，在这种情况下，绘制递归树的递归关系为 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)
于 2018-11-29T06:30:13.600 回答
11
证明答案很好，但我总是必须手动进行几次迭代才能真正说服自己。所以我在白板上画了一个小的调用树，开始计算节点。我将计数分为总节点、叶节点和内部节点。这是我得到的：
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)).
于 2014-02-28T01:21:33.270 回答
10
它的下端以 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)
如果您愿意，可以使用其封闭形式进一步减少紧密绑定。
于 2008-12-11T21:03:08.937 回答
2
通过绘制函数调用图很容易计算。只需为每个 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)
于 2019-12-20T22:40:22.527 回答
1
好吧，据我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) ].
于 2012-11-18T00:46:27.003 回答
1
由于计算中的重复，斐波那契的朴素递归版本在设计上是指数的：
从根本上讲，您正在计算：
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))
这只是一个下限，就您的分析而言应该足够了，但实时函数是相同斐波那契公式的常数因子，并且已知封闭形式是黄金比例的指数。
此外，您可以使用如下动态编程找到优化的斐波那契版本：
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
这就是成本呈指数增长的原因。
于 2017-09-30T22:21:52.600 回答
0
没有答案强调可能是计算序列的最快和最节省内存的方法。斐波那契数列有一个封闭形式的精确表达式。它可以通过使用生成函数或使用线性代数来找到，就像我现在要做的那样。
设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) 内存复杂度）或使用更好的模型（如图灵机，在这种情况下需要更多的分析。
于 2022-01-10T22:59:17.053 回答