我知道大o符号,但我不知道如何计算它的许多函数。特别是,我一直在试图弄清楚朴素版斐波那契数列的计算复杂度:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波那契数列的计算复杂度是多少?它是如何计算的?
我知道大o符号,但我不知道如何计算它的许多函数。特别是,我一直在试图弄清楚朴素版斐波那契数列的计算复杂度:
int Fibonacci(int n)
{
if (n <= 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
斐波那契数列的计算复杂度是多少?它是如何计算的?
当前回答
好吧,根据我的说法,它是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)阶。
其他回答
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}和f f {n} {n + 2} = + 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)
Since the norm of x_2 is smaller than 1, the corresponding term vanishes as n tends to infinity; therefore, obtaining the greatest integer smaller than (x_1^n)/sqrt(5) is enough to find the answer exactly. By making use of the trick of repeatedly squaring, this can be done using only O(log_2(n)) multiplication (and addition) operations. Memory complexity is even more impressive because it can be implemented in a way that you always need to hold at most 1 number in memory whose value is smaller than the answer. However, since this number is not a natural number, memory complexity here changes depending on whether if you use fixed bits to represent each number (hence do calculations with error)(O(1) memory complexity this case) or use a better model like Turing machines, in which case some more analysis is needed.
证明答案很好,但我总是不得不手工做一些迭代来真正说服自己。所以我在白板上画了一个小的调用树,并开始计算节点。我将计数分为总节点、叶节点和内部节点。以下是我得到的答案:
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),因为在这个函数中,只有递归花费了相当多的时间(分治)。我们看到,上面的函数将在树中继续存在,直到叶子趋近于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)阶。
通过绘制函数调用图来计算很简单。简单地为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)
在麻省理工学院有一个关于这个具体问题的很好的讨论。在第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:如果你想了解更多信息,维基百科上有关于第n个斐波那契数的封闭形式表达的讨论。