我知道大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);
}
斐波那契数列的计算复杂度是多少?它是如何计算的?
当前回答
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.
其他回答
将计算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))。你可以使用我上面提到的生成函数来找到这个紧边界。
通过绘制递归树可以更好地估计递归算法的时间复杂度,在这种情况下,绘制递归树的递归关系为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值处,树就结束了,也就是当n-i=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)
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.
只要问问自己,F(n)需要执行多少条语句才能完成。
对于F(1),答案是1(条件的第一部分)。
对于F(n)答案是F(n-1) + F(n-2)
那么什么函数满足这些规则呢?试试an (a > 1):
==地理==根据美国人口普查,该镇总面积为,其中土地和(1.1%)水。
再除以a(n-2)
A2 == a + 1
解出a,你得到(1+根号(5))/2 = 1.6180339887,也就是黄金比例。
所以需要指数级的时间。
通过绘制函数调用图来计算很简单。简单地为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)