注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

快速计算fibonacci数列  

2010-10-06 22:30:24|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

查看全文


Fibonacci数列是一个很常见的数列,定义很简单
Fib(0) = 1
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)
常见的计算方法主要有两种:递归和循环。
其中递归的方法最容易理解,但复杂度高。可以用备忘录的方式解决重复计算,从而取得更好的结果
第二种办法的循环,从小到大算起,fib(2)=fib(0)+fib(1), fib(3)=fib(2)+fib(1)... fib(n)=fib(n-1)+fib(n-2),只要O(n)的复杂度,是一种很另人满意的算法。
但是在编程珠玑上看到了第三种方法:矩阵相乘
Fib(i+2) = Fib(i+1) + Fib(i)
[Fib(i+2), Fib(i+1)] = [Fib(i+1)+Fib(i), Fib(i+1)] = [Fib(i+1)*1+Fib(i)*1, Fib(i+1)*1+Fib(i)*0]
=[Fib(i+1), Fib(i)] * [1, 1]
                             [1, 0]
设A=[1,1]
        [1,0]
则 [Fib(n), Fib(n-1)] = [Fib(n-1), Fib(n-2)]*A = [Fib(n-2), Fib(n-3)] * A * A
=[Fib(1), Fib(0)] * A^(n-1)
这个问题就转化成了求A^n的问题,而A^n可以表示成A^(2^i1) * (A^(2^i2)) * (A^(2^i3))的形式,因此复杂度为O(log2N)
如A^13 = A^1 * A^4 * A^8
使用C++语言对这三种算法进行比较,结果如下所示:
Fib1=165580141cost:2sec //递归计算,一轮要2秒
Fib2=165580141cost:6sec //循环计算,5000000轮要6秒,复杂度O(n)
Fib3=165580141cost:1sec //矩阵乘法,5000000轮要1秒,复杂度O(log2N)

注,还有第四种方法 Fib(n)={ [( (1+sqrt(5))/2 )^(n+1)]  - [( (1-sqrt(5))/2 )^(n+1)]  } / sqrt(5),但是这个公式只对1-9的n有效。。。

代码如下:
#include <iostream>
using namespace std;

typedef long long xint;

void mul(xint p1[][2], xint p2[][2]){
    xint tmp[2][2];
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            tmp[i][j]=p1[i][0]*p2[0][j]+p1[i][1]*p2[1][j];
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++)
            p1[i][j]=

查看全文

  评论这张
 
阅读(1276)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017