1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 其他编程语言
  4. Java

[算法基础] 从斐波那契数列说起（一）

• Java • 阅读 100

从斐波那契数列说起

斐波那契（Fibonacci）数列是数学中一个著名的数列，有很多神奇的特性，在多个领域有广泛使用。定义如下数列为斐波那契数列：

[算法基础] 从斐波那契数列说起（一）

该如何编写程序求解出斐波那契数列第n项呢？

一、递归法

根据上述公式，可以很容易用Python实现如下代码：

def fib(n):
    return n if n else fib(n - 1) + fib(n - 2)

上述程序实现简单，且可读性强，只需要一行代码即可完成。这种解法是递归算法，将f(n)拆分为f(n-1)与f(n-2)，在函数体内循环调用函数本身，直至达到终止条件f(0)与f(1)。我们以计算f(5)为例画图拆分求解过程:

[算法基础] 从斐波那契数列说起（一）

用同一种颜色标注的方块为重复计算的内容。可以看到仅仅是计算f(5)，就存在非常多的重复计算情况。我们也能发现，随着n越来越大，计算时间呈指数增长。读者可以尝试使用这种方法分别计算f(10)、f(20)、f(30)、f(40)、f(50)等，比较耗时增长的情况。实际上，该算法的时间复杂度为0(2n)级别，计算效率很低。

二、递推法

递归算法的计算过程是从后往前，一直计算到f(0)和f(1)。一种简单的办法是利用f(n)的递推公式，从前往后，这样避免了递归，用一个循环就可以直接得到结果，代码如下：

def fib_for(n):
    result = [_ for _ in range(n + 1)]
    for i in range(2, n + 1):
        result[i] = result[i - 1] + result[i - 2]
    return result[n]

这种办法存储一个长度为n+1的列表，由f(0)和f(1)计算得到f(2)，再由f(1)和f(2) 计算得到f(3)，依次类推，得到f(n)。这种方法时间复杂度为0(n)级别，会很快得到期望结果。但同时我们发现，这种方法需要占用一个n+1的列表。针对这一问题，我们可以进一步优化。

我们在计算中重复使用公式f(n)=f(n-1)+f(n-2)，而该公式只占用三个变量，且最终我们只需要获得f(n)即可，不用保留中间值。因此我们可以不要存储列表，而采用滚动赋值的方法，做如下修改：

def fib_foropt(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

这种方法将空间复杂度由0(n)降为0(1)，大幅节省了内存占用。

三、矩阵快速幂法

递推法的时间复杂度为0(n)，矩阵快速幂法可以进一步降低时间复杂度至0(logn)，当n>1时，由f(n)=f(n-1)+f(n-2)，可以得：

[算法基础] 从斐波那契数列说起（一）

重复矩阵相乘，进一步得

[算法基础] 从斐波那契数列说起（一）

[算法基础] 从斐波那契数列说起（一）

[算法基础] 从斐波那契数列说起（一）

[算法基础] 从斐波那契数列说起（一） 
  def multiply(a, b):
           c = [[0, 0], [0, 0]]
           for i in range(2):
               for j in range(2):
                   c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j])
           return c

def fib_mat(n):
    if n < 2:
        return n

    def matrix_pow(a, m):
        if m == 0:
            return 1
        if m == 1:
            return a

        res = matrix_pow(a, m >> 1)
        res = multiply(res, res)
        if m & 1:
            res = multiply(res, a)
        return res

    out = matrix_pow([[1, 1], [1, 0]], n - 1)

    return out[0][0]

分析总结

对比以上三类解法，我们可以发现，同一个问题，可以有不同的算法解决。对于斐波那契数列问题，递归法实现容易，可读性好，后期易于维护，但是运行效率低。矩阵快速幂法运行效率高，占用内存小，但实现复杂，后期维护成本高。相对而言，递推法编程比较容易，代码清晰，运算速度快，更加适用于解决该问题。

不同的算法效率不同，占用内存不同，编写复杂程度不同，后期维护的难易程度也不同。因此，在我们日常工作中，需要有意识地考虑算法的性能，平衡编程、维护、效率等方面的关系，选择合适的算法。本系列后续文章会逐步介绍算法的相关基础知识，希望在归纳整理过程中，和读者共同成长。

Original: https://www.cnblogs.com/shanxihualu/p/16731359.html
Author: 陕西华路
Title: [算法基础] 从斐波那契数列说起（一）

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619581/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球