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

我理解Big-O符号,但我不知道如何计算它的许多function。 特别是,我一直在试图弄清斐波那契数列的天真版本的计算复杂性:

int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } 

斐波纳契数列的计算复杂度是多less?它是如何计算的?

您可以将时间函数build模为将Fib(n)计算为Fib(n-1)加上计算Fib(n-2)的时间加上将它们加在一起的时间( O(1) )的时间总和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

你解决这个重复关系(例如使用生成函数),你将会得到答案。

或者,您可以绘制recursion树,其深度为n并直观地指出该函数是渐近O(2 n ) 。 然后你可以通过归纳certificate你的猜想。

基数: n = 1是显而易见的

因此,假设T(n-1) = O(2 n-1 )

T(n) = T(n-1) + T(n-2) + O(1) 等于

T(n) = O(2 n-1 ) + O(2 n-2 ) + O(1) = O(2 n )

但是,正如评论所指出的那样,这并不是一个严格的界限。 关于这个函数的一个有趣的事实是T(n)与Fib(n)的值渐近地相同 ,因为它们都被定义为

f(n) = f(n-1) + f(n-2)

recursion树的叶子将总是返回1. Fib(n)的值是recursion树中叶子返回的所有值的和,等于树叶的数量。 由于每一片叶片都将采用O(1)进行计算,因此T(n)等于Fib(n) x O(1) 。 因此,这个函数的紧束缚是斐波那契数列本身( θ(1.6 n ) )。 你可以通过使用上面提到的生成函数来找出这个紧密的界限。

只要问自己需要执行多less条语句才能完成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)

a 2 == a + 1

解决a和你得到(1+sqrt(5))/2 = 1.6180339887 ,否则被称为黄金比例 。

所以需要指数的时间。

麻省理工学院对这个具体问题有一个很好的讨论。 在第5页,他们指出,如果你假设一个加法需要一个计算单位,计算Fib(N)所需的时间与Fib(N)的结果非常相关。

因此,您可以直接跳至斐波那契数列的非常接近的近似值:

 Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately) 

并且说,因此,朴素algorithm的最坏情况的性能是

 O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1)) 

PS:如果你想了解更多的信息,可以参考Wikipedia 上第N个斐波纳契数的封闭expression式 。

我同意pgaur和rickerbh,recursion斐波那契的复杂度是O(2 ^ n)。

我以相当简单的方式得出了相同的结论,但我相信仍然是有效的推理。

首先,计算第N个斐波纳契数时,要计算多less次recursion斐波那契函数(F()从现在起)被调用。 如果在序列0到n中每个数字被调用一次,那么我们有O(n),如果每个数字被调用n次,那么我们得到O(n * n)或O(n ^ 2)等等。

所以,当F()被调用到数n时,在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)被调用了多less次,我们可以看到F(0)被调用的次数只是其中的一部分。

如果我们从F(6)到F(2)的所有行从心理上移动到F(1)行,我们可以看到现在F(1)和F(0)行的长度是相等的。 这意味着当n = 6时F()被调用的总次数是2×32 = 64 = 2 ^ 6。

现在,就复杂性而言:

 O( F(6) ) = O(2^6) O( F(n) ) = O(2^n) 

它的下限为2^(n/2) ,上限为2 ^ n(如其他评论所述)。 这个recursion实现的一个有趣的事实是它有一个Fib(n)本身的紧的渐近界。 这些事实可以概括为:

 T(n) = Ω(2^(n/2)) (lower bound) T(n) = O(2^n) (upper bound) T(n) = Θ(Fib(n)) (tight bound) 

如果你愿意的话,可以用封闭的forms进一步减less紧密的边界。

certificate答案是好的,但我总是需要手动做一些迭代才能真正说服自己。 于是我在白板上画出了一个小小的调用树,并开始计算节点。 我将我的计数分成总节点,叶节点和内部节点。 这是我得到的:

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

那么,据我所知这是O(2^n)在这个函数中只有recursion占用相当的时间(分而治之)。 我们看到,上面的函数将继续在一棵树上,直到当叶子达到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) ]

你可以扩大它,并可视化

  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(ni) ... ==> O(2^n) 

由于计算中的重复,斐波那契的天真recursion版本是指数devise的:

在你正在计算的根源上:

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个recursion调用,在计算中浪费了大量的数据,时间函数看起来是这样的:

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

这只是一个下限,为了您的分析的目的应该是足够的,但实时函数是由相同的斐波那契公式的一个常数的因素,并且已知封闭forms是黄金比率的指数。

另外,你可以使用这样的dynamic编程来find斐波那契的优化版本:

 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步,但也是指数。

成本函数是从input大小到解决问题的步骤数量定义的。 当你看到Fibonacci的dynamic版本( n个步骤来计算表)或最简单的algorithm来知道一个数字是否为素数( sqrt(n)来分析数字的有效除数)。 你可能会认为这些algorithm是O(n)或者O(sqrt(n)),但是这是不正确的,原因如下:algorithm的input是一个数字: n ,使用二进制表示法input整数nlog2(n)然后做一个variables的变化

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

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

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

那么作为input大小函数的algorithm的成本是:

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

这就是为什么成本是一个指数。

这performance得更好:

 unsigned int Fib(unsigned int n) { // first Fibonaci number is Fib(0) // second one is Fib(1) and so on // unsigned int m; // m + current_n = original_n unsigned int a = 1; // Fib(m) unsigned int b = 0; // Fib(m-1) unsigned int c = 0; // Fib(m-2) while (n--) { c = b; b = a; a = b+c; } return a; }