Bis*_*Das 74 algorithm math performance fibonacci time-complexity
是否有任何算法来计算子线性时间内的第n个斐波纳契数？
Pet*_*ham 97
根据Pillsy对矩阵求幂的引用,对于矩阵
M = [1 1]
[1 0]
然后
fib(n) = Mn1,2
使用重复乘法将矩阵提升到幂并不是非常有效.
矩阵求幂的两种方法是分而治之,其在O(ln n)步骤中产生M n,或者是恒定时间的特征值分解,但是由于有限的浮点精度可能引入误差.
如果希望精确值大于浮点实现的精度,则必须使用基于此关系的O(ln n)方法:
Mn = (Mn/2)2 if n even = M·Mn-1 if n is odd
M上的特征值分解找到两个矩阵U和Λ,使得Λ是对角线和
M = U Λ U-1
Mn = ( U Λ U-1) n
= U Λ U-1 U Λ U-1 U Λ U-1 ... n times
= U Λ Λ Λ ... U-1
= U Λ n U-1
养对角矩阵Λ的Ñ次方是在提高各个元件的一个简单的事情 Λ到Ñ个,所以这给出了提高的O(1)方法中号至Ñ次方.但是,Λ中的值不可能是整数,因此会出现一些错误.
为我们的2x2矩阵定义Λ
Λ = [ λ1 0 ] = [ 0 λ2 ]
为了找到每个λ,我们解决了
|M - λI| = 0
这使
|M - λI| = -λ ( 1 - λ ) - 1 λ² - λ - 1 = 0
使用二次方程式
λ = ( -b ± √ ( b² - 4ac ) ) / 2a
= ( 1 ± √5 ) / 2
{ λ1, λ2 } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2
如果您已经阅读了杰森的答案,您可以看到这将会发生什么.
求解特征向量X 1和X 2:
if X1 = [ X1,1, X1,2 ] M.X1 1 = λ1X1 X1,1 + X1,2 = λ1 X1,1 X1,1 = λ1 X1,2 => X1 = [ Φ, 1 ] X2 = [ 1-Φ, 1 ]
这些向量给出U:
U = [ X1,1, X2,2 ]
[ X1,1, X2,2 ]
= [ Φ, 1-Φ ]
[ 1, 1 ]
使用反转U.
A = [ a b ]
[ c d ]
=>
A-1 = ( 1 / |A| ) [ d -b ]
[ -c a ]
所以U -1由.给出
U-1 = ( 1 / ( Φ - ( 1 - Φ ) ) [ 1 Φ-1 ]
[ -1 Φ ]
U-1 = ( √5 )-1 [ 1 Φ-1 ]
[ -1 Φ ]
完整性检查:
UΛU-1 = ( √5 )-1 [ Φ 1-Φ ] . [ Φ 0 ] . [ 1 Φ-1 ]
[ 1 1 ] [ 0 1-Φ ] [ -1 Φ ]
let Ψ = 1-Φ, the other eigenvalue
as Φ is a root of λ²-λ-1=0
so -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 1
UΛU-1 = ( √5 )-1 [ Φ Ψ ] . [ Φ 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψ ] [ -1 Φ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φ -ΨΦ ]
[ 1 1 ] [ -Ψ ΨΦ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φ 1 ]
[ 1 1 ] [ -Ψ -1 ]
= ( √5 )-1 [ Φ²-Ψ² Φ-Ψ ]
[ Φ-Ψ 0 ]
= [ Φ+Ψ 1 ]
[ 1 0 ]
= [ 1 1 ]
[ 1 0 ]
= M
所以理智检查成立.
现在我们有了计算M n 1,2所需的一切:
Mn = UΛnU-1
= ( √5 )-1 [ Φ Ψ ] . [ Φn 0 ] . [ 1 -Ψ ]
[ 1 1 ] [ 0 Ψn ] [ -1 Φ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φn -ΨΦn ]
[ 1 1 ] [ -Ψn ΨnΦ ]
= ( √5 )-1 [ Φ Ψ ] . [ Φn Φn-1 ]
[ 1 1 ] [ -Ψn -Ψn-1 ] as ΨΦ = -1
= ( √5 )-1 [ Φn+1-Ψn+1 Φn-Ψn ]
[ Φn-Ψn Φn-1-Ψn-1 ]
所以
fib(n) = Mn1,2
= ( Φn - (1-Φ)n ) / √5
这与其他地方给出的公式一致.
您可以从重复关系推导出它,但在工程计算和模拟中计算大矩阵的特征值和特征向量是一项重要的活动,因为它给出了方程组的稳定性和谐波,并允许有效地将矩阵提高到高功率.
jas*_*son 64
所述n第Fibonacci数由下式给出
f(n) = Floor(phi^n / sqrt(5) + 1/2)
哪里
phi = (1 + sqrt(5)) / 2
假设原始数学运算(+,-,*和/)是O(1)可以使用该结果来计算n在第Fibonacci数O(log n)时间(O(log n)因为式中的求幂的).
在C#中:
static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use
const double inverseSqrt5 = 0.44721359549995793928183473374626
const double phi = 1.6180339887498948482045868343656
*/
static int Fibonacci(int n) {
return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}
yai*_*chu 55
如果你想要确切的数字(这是一个"bignum",而不是一个int/float),那我恐怕
不可能!
如上所述,斐波纳契数的公式为:
FIB N =地板(PHI ñ /√5+ 1/2)
fib n~ = phi n /√5
多少位数fib n？
numDigits(fib n)= log(fib n)= log(phi n /√5)= log phi n - log√5= n*log phi - log√5
numDigits(fib n)= n*const + const
这是O(n)
由于请求的结果是O(n),因此不能在小于O(n)的时间内计算.
如果您只想要答案的低位数,则可以使用矩阵求幂方法在子线性时间内计算.
Pil*_*lsy 24
您也可以通过对整数矩阵进行取幂来实现.如果你有矩阵
/ 1 1 \
M = | |
\ 1 0 /
然后(M^n)[1, 2]将等于n第Fibonacci数,如果[]是矩阵下标并且^是矩阵求幂.对于固定大小的矩阵,可以在O(log n)时间内以与实数相同的方式对正整数幂进行取幂.
编辑:当然,根据您想要的答案类型,您可以使用恒定时间算法.像其他公式所显示的那样,n斐波那契数量呈指数增长n.即使使用64位无符号整数,您也只需要一个94条目的查找表来覆盖整个范围.
第二次编辑:首先使用特征分解进行矩阵指数与下面的JDunkerly解决方案完全相同.该矩阵的特征值是(1 + sqrt(5))/2和(1 - sqrt(5))/2.
维基百科有一个封闭的表格解决方案 http://en.wikipedia.org/wiki/Fibonacci_number
或者在c#中:
public static int Fibonacci(int N)
{
double sqrt5 = Math.Sqrt(5);
double phi = (1 + sqrt5) / 2.0;
double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
return (int)fn;
}
| 归档时间： |
|
| 查看次数： |
37883 次 |
| 最近记录： |