快速计算斐波那契数的方法

公式:

使用 exponentiation by squaring 你会得到一个 O(log(n)) 乘法求第n个斐波那契数。但在这种情况下,乘法并不是一个简单的操作,实际的时间复杂度是 O(M(n)*log(n)) 哪里 M(n) 是两个数与长度相乘的复杂性 O(n) .

有一个 benchmark 在计算斐波那契数的几种算法中,包括带朴素乘法的矩阵方法和Karatsuba乘法。

还有一个直接公式-斐波那契序列是线性递归关系,第n个元素有一个已知的精确公式。公式为:

其中phi是 golden ratio psi是它的反比。

O(log(n)) 乘法。 phi是一个浮点数,因此可能会因舍入大数而出错。

P、 我碰巧写过 a blog post on the problem . 你也可以看看 wikipedia has to say about it .