众所周知,生成斐波那契数列的最简单算法如下:
if(n<=0) return 0;
else if(n==1) return 1;
f(n) = f(n-1) + f(n-2);
但是这个算法有一些重复的计算。例如,如果你计算f(5),它将计算f(4)和f(3)。当你计算f(4)时,它将再次计算f(3)和f(2)。有没有更加时间高效的递归算法呢?
我已经了解了一些计算斐波那契数列的时间复杂度高效的方法,以下是其中一些——
方法1-动态规划 现在这里的子结构通常是已知的,因此我将直接跳到解决方案——
static int fib(int n)
{
int f[] = new int[n+2]; // 1 extra to handle case, n = 0
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
static int fib(int n)
{
int a = 0, b = 1, c;
if (n == 0)
return a;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
方法2-(使用矩阵{{1,1},{1,0}}的幂)
这是一种O(n)的算法,它依赖于这样一个事实:如果我们将矩阵M={{1, 1}, {1, 0}}自乘n次(换句话说,计算power(M,n)),那么我们可以得到第(n+1)个斐波那契数作为结果矩阵中行和列(0,0)处的元素。该解决方案需要O(n)时间。
矩阵表示法给出了以下闭合表达式的斐波那契数: fibonaccimatrix
static int fib(int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/*multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/*function that calculates F[][] raise to the power n and puts the
result in F[][]*/
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][]{{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
这可以通过优化,使时间复杂度为O(Logn)。我们可以使用递归乘法在先前的方法中计算power(M, n)。
static int fib(int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
static void multiply(int F[][], int M[][])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
static void power(int F[][], int n)
{
if( n == 0 || n == 1)
return;
int M[][] = new int[][]{{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
方法3(O(log n)时间复杂度) 下面是另一个有趣的递推公式,可以用来在O(log n)的时间内找到第n个斐波那契数。
如果n是偶数,则k = n/2: F(n) = [2*F(k-1) + F(k)]*F(k)
如果n是奇数,则k = (n+1)/2: F(n) = F(k)*F(k) + F(k-1)*F(k-1) 这个公式是如何工作的呢? 可以从上面的矩阵方程中推导出该公式。 fibonaccimatrix
对两边取行列式,得到 (-1)n = Fn+1Fn-1 – Fn2 并且,由于对于任意方阵A,AnAm = An+m,因此可以推出以下恒等式(它们是从矩阵乘积的两个不同系数中得到的)
FmFn + Fm-1Fn-1 = Fm+n-1
通过将n = n+1代入上式,得到
FmFn+1 + Fm-1Fn = Fm+n
将m = n代入上式,得到
F2n-1 = Fn2 + Fn-12
F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn(来源:维基百科)
为了得到要证明的公式,我们只需要按照以下步骤进行即可: 如果n是偶数,我们可以令k = n/2 如果n是奇数,我们可以令k = (n+1)/2
public static int fib(int n)
{
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
// If fib(n) is already computed
if (f[n] != 0)
return f[n];
int k = (n & 1) == 1? (n + 1) / 2
: n / 2;
// Applyting above formula [See value
// n&1 is 1 if n is odd, else 0.
f[n] = (n & 1) == 1? (fib(k) * fib(k) +
fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k))
* fib(k);
return f[n];
}
方法四 - 使用公式 在此方法中,我们直接实现斐波那契数列的第n项公式。时间复杂度O(1),空间复杂度O(1)。 Fn = {[(√5 + 1)/2] ^ n} / √5
static int fib(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n)
/ Math.sqrt(5));
}
参考文献: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
该网址提供了关于斐波那契数列的公式和相关信息。查看用Erlang实现的内容,它使用公式:。它表现出良好的线性结果行为,因为在
O(M(n) log n)
的一部分中,对于大数,M(n)
是指数级的。它可以在 2 秒内计算出具有 208988 位数字的一百万斐波那契数。诀窍在于,您可以使用(尾递归)公式(尾部意味着具有 O(1)
的空间,当使用适当的编译器或重写为循环时),在 O(log n)
个乘法中计算出幂:
% compute X^N
power(X, N) when is_integer(N), N >= 0 ->
power(N, X, 1).
power(0, _, Acc) ->
Acc;
power(N, X, Acc) ->
if N rem 2 =:= 1 ->
power(N - 1, X, Acc * X);
true ->
power(N div 2, X * X, Acc)
end.
在这里,您需要用矩阵替换 X
和 Acc
。 X
将被初始化为 ,而
Acc
则是等于恒等矩阵 I
,即 。
一种简单的方式是迭代计算而不是递归计算。这样可以在线性时间内计算出F(n)。
def fib(n):
a,b = 0,1
for i in range(n):
a,b = a+b,a
return a
O(M(n)log n)
的时间复杂度内计算,其中M(n)
是乘法成本。对于大数,您的代码实际上是O(n^2)
。请参阅我的答案,以获得快速准确的大数计算。无论如何,您都必须使用一些支持此功能的大数库或语言。 - Hynek -Pichi- Vychodil您可以保存您的结果并使用它们:
public static long[] fibs;
public long fib(int n) {
fibs = new long[n];
return internalFib(n);
}
public long internalFib(int n) {
if (n<=2) return 1;
fibs[n-1] = fibs[n-1]==0 ? internalFib(n-1) : fibs[n-1];
fibs[n-2] = fibs[n-2]==0 ? internalFib(n-2) : fibs[n-2];
return fibs[n-1]+fibs[n-2];
}
提示:您可以使用比内公式来实现更快的结果:
以下是在Python中实现的方法:
from decimal import *
def fib(n):
return int((Decimal(1.6180339)**Decimal(n)-Decimal(-0.6180339)**Decimal(n))/Decimal(2.236067977))
// D Programming Language
void vFibonacci ( const ulong X, const ulong Y, const int Limit ) {
// Equivalent : if ( Limit != 10 ). Former ( Limit ^ 0xA ) is More Efficient However.
if ( Limit ^ 0xA ) {
write ( Y, " " ) ;
vFibonacci ( Y, Y + X, Limit + 1 ) ;
} ;
} ;
// Call As
// By Default the Limit is 10 Numbers
vFibonacci ( 0, 1, 0 ) ;
F(n) = (φ^n)/√5,四舍五入到最近的整数,其中φ是黄金比例。
φ^n可以在O(lg(n))时间内计算,因此F(n)可以在O(lg(n))时间内计算。
编辑:我认为Hynek Vychodil的答案比我的更好,但我还是保留这个答案以防有人寻找其他方法。
我认为其他方法都是有效的,但不是最优的。使用Binet公式原则上应该可以给出正确答案,但将其四舍五入到最近的整数会在n很大时产生一些问题。其他解决方案将不必要地重新计算每次调用函数时的值,因此该函数不适用于重复调用优化。
在我看来,最好的做法是定义一个全局数组,然后在需要时向数组添加新值。在Python中:
import numpy
fibo=numpy.array([1,1])
last_index=fibo.size
def fib(n):
global fibo,last_index
if (n>0):
if(n>last_index):
for i in range(last_index+1,n+1):
fibo=numpy.concatenate((fibo,numpy.array([fibo[i-2]+fibo[i-3]])))
last_index=fibo.size
return fibo[n-1]
else:
print "fib called for index less than 1"
quit()
如果你需要调用 n>80 的 fib 函数(大约),那么你将需要在 Python 中实现任意精度整数,这在 Python 中很容易做到。
这将执行得更快,O(n)
def fibo(n):
a, b = 0, 1
for i in range(n):
if i == 0:
print(i)
elif i == 1:
print(i)
else:
temp = a
a = b
b += temp
print(b)
n = int(input())
fibo(n)
f(n - 1) = f(n - 2) + f(n - 3)
所以f(n) = 2 * f(n - 2) + f(n - 3)
。你可以缓存f(n - 2)
。当然,如果你选择的编程语言有yield
,那么迭代实现会更好。 - Ry-