搜索:
首页 >> JavaScript >> Js高级编程 >> Fibonacci数,Θ(log n)

Fibonacci数,Θ(log n)

2010-3-28 作者:infinte 来源:infinte博客 投递文章

生成Fiboncci Fn数有Θ(1),Θ(n)甚至指数级的算法,不过有Θ(log n)的吗?告诉你,有。

首先,关于Fibonacci数,有下面的定理(假设F0 = 0,n≥2)

证明可以用归纳法,n=2时不证自明,假设n=k-1时成立,那么n=k时,

现在,计算F(n)的问题就转化到计算矩阵上来。不过现在问题已经很明晰了——反复平方法。

下面是js源码:

var fib = function() {
var f = function(n, a, b, p, q) {
if (n == 0) return b;
if (n & 1) return f(n - 1, b * q + a * q + a * p, b * p + a * q, p, q)
else return f(n >>> 1, a, b, q * q + p * p, q * (2 * p + q));
}
return function(n) {
return f(n, 1, 0, 0, 1)
};
}();
Tags:Fibonacci  函数  数学  算法 
相关文章
手机版 Js高级编程 Asp之家 Aspxhome.com
闽ICP备06017341号