Jul*_*iet 310 complexity-theory big-o fibonacci time-complexity
我理解Big-O表示法,但我不知道如何为许多函数计算它.特别是,我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci序列的计算复杂度是多少以及如何计算？
Meh*_*ari 349
您将时间函数建模为计算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).因此,该函数的紧束缚是Fibonacci序列本身(〜).你可以通过使用我上面提到的生成函数找出这个紧密的界限.?(1.6n)
Jas*_*hen 121
只要问问自己需要执行多少语句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,或称为黄金比例.
所以它需要指数时间.
J.P*_*.P. 30
我同意pgaur和rickerbh,recursive-fibonacci的复杂性是O(2 ^ n).
我以相当简单的方式得出了相同的结论,但我相信仍然是有效的推理.
首先,它是关于计算在计算第N个斐波那契数时调用递归的斐波那契函数(从现在开始的F())的次数.如果在序列0到n中每个数字调用一次,那么我们有O(n),如果每个数字被调用n次,那么我们得到O(n*n)或O(n ^ 2),等等.
因此,当为数字n调用F()时,对于0和n-1之间的给定数字,调用F()的次数随着接近0而增加.
作为第一印象,在我看来,如果我们以可视方式放置它,每次为一个给定的数字调用F()绘制一个单位,wet得到一种金字塔形状(也就是说,如果我们水平居中单位) ).像这样的东西:
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)
Bob*_*oss 29
麻省理工学院对这个具体问题进行了非常好的讨论.在第5页,他们指出,如果你假设一个加法需要一个计算单位,那么计算Fib(N)所需的时间与Fib(N)的结果密切相关.
因此,您可以直接跳到Fibonacci系列的非常接近的近似值:
Fib(N) = (1/sqrt(5)) * 1.618^(N+1) (approximately)
并且因此说,天真算法的最坏情况表现是
O((1/sqrt(5)) * 1.618^(N+1)) = O(1.618^(N+1))
PS:如果您想了解更多信息,请在维基百科上讨论Nth Fibonacci数字的封闭形式表达式.
Ton*_*ous 15
您可以扩展它并进行可视化
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)
它位于下端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)
如果您愿意,可以使用封闭形式进一步减少紧密限制.
证明答案是好的,但我总是需要手工做几次迭代才能真正说服自己.所以我在我的白板上画了一个小的调用树,并开始计算节点.我将计数分为总节点,叶节点和内部节点.这是我得到的:
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)+ O(1)注意每一步都需要O(1)意味着恒定的时间,因为如果 block.Recursion树看起来只有一个比较来检查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)