代码之家  ›  专栏  ›  技术社区  ›  trafalgarLaww

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

  •  0
  • trafalgarLaww  · 技术社区  · 7 年前

    enter image description here

    我说得对吗?

    方法来自 here .

    2 回复  |  直到 7 年前
        1
  •  5
  •   DAle    7 年前

    公式:

    enter image description here

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

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

        2
  •  0
  •   Nikola Dimitroff    7 年前

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

    fibonacci formula

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

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

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