Fibonacci数的巧妙求法

看MIT算法导论视频真是收获不蜚,今天学会了求Fibonacci数最快的方法~

Fibonacci(斐波那契)数列小学生都知道的,求Fibonacci数也不是什么难事,可以用递推式一步一步推(线性)。有没有更快的方法呢,你可能马上就想到了通项公式:

这个公式要算一个数的n次方,由于一个数的n次方可以由一个分治算法在logn时间内得到:
power of n

所以这个算法时间复杂度是O(logn)的。推导没有错误,但是忽略了一个问题:精度。无理数只能近似表示,所以无理数的乘方是有误差的,而且误差越乘越大,所以需要足够多的有效位数才能保证最后的答案是正确的。由于是取最近的整数,只要误差超过0.5,结果就会出错。如果n很大,比如说1亿,这个算法就得几乎不可到正确结果。而下面的算法则避开了这个问题。

设Fibonacci数列的第n个数是Fn,则有:

Fibonacci 好吧,一个2*2的matrix就解决问题,真是精妙的算法。这个公式可以轻松的用数学归纳法验证。由于计算过程中都是整数,所以不会出现精度问题。两个2*2的矩阵相乘复杂度O(1),矩阵的乘方也可用上面的分治算法求得,所以 T(n) = T(n/2) + O(1),由主定理解得 T(n) = O(logn)。

MIT的算法导论课程视频和讲义VeryCD上有:Click me.  主讲老师就是《算法导论》的主要作者之一:Charles E. Leiseson (中文版封底上有他的照片),讲得非常好,通俗易懂,还可以顺带练习英语听力~~强烈推荐

This entry was posted in 技术学习 and tagged , , . Bookmark the permalink.

2 Responses to Fibonacci数的巧妙求法

  1. 5x says:

    对一般k阶常系数递推数列
    f(n) = a1*f(n-1) + a2*f(n-2) + … + ak*f(n-k)
    可以构造出k阶转移矩阵:
    a1 a2 … ak
    1 0 … 0
    0 1 … 0

    0 0 ..1 0

    然后左乘初值向量(fk,f(k-1), … f0)’

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据