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

Question

如果我将使用以下方法计算斐波那契数，它将比线性方法更快:

我说得对吗？

方法来自here .

Answer 1

公式:

使用 exponentiation by squaring你会得到一个 O(log(n)) 乘法来找到第 n 个斐波那契数。但是在这种情况下，乘法不是一个简单的运算，实际时间复杂度是 O(M(n)*log(n)) 其中 M(n) 是一个两个长度为 O(n) 的数字相乘的复杂度。

有一个benchmark计算斐波那契数列的几种算法，包括具有朴素乘法和 Karatsuba 乘法的矩阵方法。