Fibonacci数，Θ(log n)
作者：infinte 来源：infinte博客 发布时间：2010-03-28 13:28:00
标签：Fibonacci,函数,数学,算法
生成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)};}();
0
投稿猜你喜欢
- 有个简单的方法，使用display:table, display:table-row and display:table-cell 就可以实
- 用途：图片经常使用onload来改变宽度，但这样会出现图片的闪烁，这个简单的类就是用来解决这个问题的。函数loadImage，用来加载图片，
- 一、控制用户存取 1、创建修改用户Creating Users Create/alter user new_user identified
阅读上一篇：你是真正的用户体验设计者吗? Ⅲ交互系统设计者负责用户体验——不！那么什么是真正的交互呢?什么是交互式系统？你桌子上的杯子是交互- 在开发C/S结构的大型数据库应用软件时，一般情况下，软件开发人员和数据库设计人员并不是同一个人，这就需要协商好一些即可由程序设
- 在给客户做个程序时,突然遇到个问题,就是产品页用户提交视频播放文件时,如何根据提交的网址内的视频格式进行正确的播放呢....郁闷了一会,想好
- 很久没写过东西了，今天看了chinahuman 的《用asp自动解析网页中的图片地址，并将其保存到本地服务器》，于是优化了这个程序，并且将所
- 前两天，编辑建议我去当当和卓越申请个用户，在网站上放上我的书的链接，这样还可以拿到一些反点儿，于是我兴冲冲地跑到几个网站上去看，却只在卓越（
- 首先来看，ASP读取ACCESS数据库。代码如下:<％ @language="VBScript"&nbs
- 从大的发展来看，网站就是一块试验田，一块在错误中成长、在错误中变强变大的试验田。这决定了互联网产品的成长路线，一定是一个反复修正和迭代的曲线
- 今天我们继续向大家介绍一款翻页效果的制作。当鼠标移动到链接上时，翻页的链接区除了有悬停效果，还会放大。这样的效果具有很强烈的效果。大家适当美
- 一段时间以来，发现有很多人XHTML都不会用，不光是普通的初学者，有的程序员都不是很清楚该怎么写这个XHTML，我这里呢算是把一些常见的应用
- 两个并发事务同时访问数据库表相同的行时，可能存在以下三个问题：1、幻想读：事务T1读取一条指定where条件的语句，返回结果集。此时事务T2
- 摘要：本文主要就数据库恢复与系统任务的调度，在结合一般性的数据库后台处理的经验上，提出较为实用而新颖的解决方法，拓宽了数据库后台开发的思路。
- IE在处理透明度上真够恶心，而且在IE7必须让元素的hasLayout为ture，要不会失效。以下是我最新处理透明度的代码：var
- SQL Server 2005数据库中增加了XML类型，在创建表的时候可以指定某一列为XML类型，示例如下：CREATE TABL
- 网页制作中用到的特效字，你一定是用图象处理软件制作的吧！告诉你，不用图象处理软件，我也能做出漂亮的特效字来，你看，阴影字我就是这样做出来的。
- 字符函数——返回字符值这些函数全都接收的是字符族类型的参数(CHR除外)并且返回字符值.除了特别说明的之外,这些函数大部分返回VARCHAR
- 前两天看的时候，所用的歌曲地址加密方式已变更。将以前的发出来供大家赏玩。解密函数是从flash里面反编译出来的，加密函数是自己根据解密函数写
- JS在firefox中的兼容性问题,自己也经常遇到.此文是网上资料,不过时间较久不记得原址了...1. document.form.item
