花式破解斐波那契数列

简介: 斐波那契数列想必大家都听过,如果感觉斐波那契数列有点陌生的同学,肯定是没有好好学算法。一般在讲解递归的时候,我们都会拿出斐波那契数列这个例子来,因为它实在太经典了,今天我们就来深入研究一下斐波那契数列的解法。

什么是斐波那契数列?

数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。他当时是这样提出的:假设一对刚出生的小兔一个月后就能长成大兔,再过一个月就能生下一对小兔,并且此后每个月都生一对小兔,一年内没有发生死亡,问:一对刚出生的兔子,一年内繁殖成多少对兔子?

形成数列就是:0、1、1、2、3、5、8、13、21、34、……

在数学上,斐波那契数列以如下被以递推的方法定义:F( 0 )=0,F( 1 )=1, F( n )=F( n - 1 ) + F( n - 2 )(n ≥ 2,n ∈ N*)

解法一:递归

时间复杂度:O(2ⁿ)

空间复杂度:O(1)

斐波那契数列就是为递归而生的,我们从题中就可以找到它的规律就是后一个数是前两个数之和,它的边界就是F( 0 )=0,F( 1 )=1,它的递归调用就是 F( n - 1 ) + F( n - 2 ) 。

原理图:

image.png

代码如下:

public int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

解法二:记忆化搜索(备忘录算法)

时间复杂度:O(n)

空间复杂度:O(n)

通过上边递归的原理图片可以看出,递归时大量的中间数据是存在重复计算的,我们将这些重复的中间值通过Map缓存起来,这样同样的值我们只需要递归计算一次,就能得到解,能够极大的提高递归的效率,这就是记忆化搜索。

此种算法,是典型的用空间换时间,有n个数我们就需要缓存n个值。

优化后我们需要的计算量,是不是大幅提升呢,从下图就可以得到答案

image.png

代码如下:

public int fibonacci(int n, Map<Integer,Integer> cache) {
    if (n < 2) {
        return n;
    }
    if (cache.containsKey(n)) {
        return cache.get(n);
    }
    int value = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
    cache.put(n,value);
    return value;
}

解法三:动态规划

时间复杂度:O(n)

空间复杂度:O(1)

递归是一种自顶向下求解的过程,那么我们能不能自低向上求解呢?

自低向上就是说我们由F( 0 )=0,F( 1 )=1,F( 2 )...F( n )这样是不是更好呢?很显然可以的。

正是由于斐波那契数存在这种递推关系,所以我们可以使用动态规划求解。动态规划的状态转移方程即为上述递推关系,边界条件为 F(0) 和 F(1)。

根据动态规划的状态转移方程和边界条件,我们可以得到时间复杂度和空间复杂度都是 O(n) 的实现。由于 F(n) 只和 F(n−1) 与 F(n−2) 有关,因此可以使用 【滚动数组思想】 把空间复杂度优化成 O(1)。

代码如下:

public int fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

解法四:矩阵快速幂

时间复杂度:O(logn)

空间复杂度:O(1)

动态规划的时间复杂度是 O(n)。我们可以使用矩阵快速幂的方法来降低时间复杂度。

首先构建递推关系:

image.png

得到

image.png

image.png

public int fibonacci(int n) {
    if (n < 2) {
        return n;
    }
    int[][] q = {{1, 1}, {1, 0}};
    int[][] res = pow(q, n - 1);
    return res[0][0];
}
​
public int[][] pow(int[][] a, int n) {
    int[][] ret = {{1, 0}, {0, 1}};
    while (n > 0) {
        if ((n & 1) == 1) {
                ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}
​
public int[][] multiply(int[][] a, int[][] b) {
    int[][] c = new int[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
        }
    }
    return c;
}

解法五:通项公式

斐波那契数 F(n) 是齐次线性递推,根据递推方程 F(n)=F(n-1)+F(n-2),

可以写出这样的特征方程:x²=x+1

image.png

代码中pow 函数的时间、空间复杂度与 CPU 支持的指令集相关,这里不深入分析。

代码如下:

public int fibonacci(int n) {
    double sqrt5 = Math.sqrt(5);
    double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
    return (int) Math.round(fibN / sqrt5);
}

说明:

解法四,解法五是在LeetCode题解中上发现的,效率是真的高,但我看的也是模棱两可,这些都是高等数学的相关知识点,感兴趣的可以深入研究一下,算法的尽头还是数学啊!!!

前三个解法是我们每个人都应该掌握的。

目录
相关文章
|
JSON JavaScript API
Node.js(nodejs)对本地JSON文件进行增、删、改、查操作(轻车熟路)
Node.js(nodejs)对本地JSON文件进行增、删、改、查操作(轻车熟路)
|
存储 缓存 监控
安谋科技(Arm China)马闯:Arm架构下性能分析与优化介绍
2023年9月19日,系列课程第九节《Arm®架构下性能分析与优化介绍》正式上线,由安谋科技 (Arm China)主任工程师马闯主讲,内容涵盖:Arm架构下性能监控单元 (PMU) 介绍、Arm统计性能分析扩展 (SPE) 介绍、Arm性能分析工具介绍、Arm架构下性能优化案例分享,本期节目在阿里云官网、阿里云微信视频号、阿里云钉钉视频号、InfoQ官网、阿里云开发者微信视频号、阿里云创新中心直播平台 & 微信视频号同步播出,同时可以点击【https://developer.aliyun.com/topic/ecs-yitian】进入【倚天实例迁移课程官网】了解更多内容。
|
10月前
|
编译器
if-else对比switch-case
`if-else`和 `switch-case`是两种常用的控制流语句,各有优缺点和适用场景。`if-else`语句灵活性高,适用于复杂的条件判断;而 `switch-case`语句结构清晰,适用于处理固定的离散值。在实际应用中,根据具体需求选择合适的控制流语句,可以编写出高效、可维护的代码。
270 6
|
机器学习/深度学习 数据可视化
FredNormer: 非平稳时间序列预测的频域正则化方法
FredNormer是一种创新的频域正则化方法,旨在提高时间序列预测模型处理非平稳数据的能力。现有正则化技术虽在分布偏移上有所成效,但在频域动态模式捕捉方面存在不足。FredNormer通过自适应增强关键频率分量的权重,解决了这一问题,并设计了即插即用模块,便于集成到各类预测模型中。实验表明,FredNormer在多个公共数据集上显著提升了预测精度,特别是在复杂频率特征的数据集上效果显著。此外,其计算效率也优于现有方法。该方法为非平稳时间序列预测提供了有力工具。
267 3
FredNormer: 非平稳时间序列预测的频域正则化方法
|
存储 NoSQL JavaScript
MongoDB存储过程实战:聚合框架、脚本、最佳实践,一文全掌握!
【8月更文挑战第24天】MongoDB是一款备受欢迎的文档型NoSQL数据库,以灵活的数据模型和强大功能著称。尽管其存储过程支持不如传统关系型数据库,本文深入探讨了MongoDB在此方面的最佳实践。包括利用聚合框架处理复杂业务逻辑、封装业务逻辑提高复用性、运用JavaScript脚本实现类似存储过程的功能以及考虑集成其他工具提升数据处理能力。通过示例代码展示如何创建订单处理集合并定义验证规则,虽未直接实现存储过程,但有效地演示了如何借助JavaScript脚本处理业务逻辑,为开发者提供更多实用指导。
239 2
|
JavaScript 前端开发
JS二进制转10进制、十六进制
JS二进制转10进制、十六进制 【8月更文挑战第9天】
410 6
|
人工智能 自然语言处理
通义听悟AI能力问题之通义听悟定义如何解决
通义听悟AI能力问题之通义听悟定义如何解决
422 0
|
缓存 算法 安全
被追着问UUID和自增ID做主键哪个好,为什么?
讨论了UUID和自增ID作为数据库主键的优缺点。UUID全局唯一,适合分布式系统,但存储空间大,不适合范围查询。自增ID存储空间节省,查询效率高,但分库分表困难,可预测性高。UUID版本包括基于时间戳(V1)、随机数(V4)以及基于名称空间的MD5(V3)和SHA1(V5)散列。
被追着问UUID和自增ID做主键哪个好,为什么?
|
SQL Java 数据库连接
17:数据库连接池与Servlet整合-Java Web
17:数据库连接池与Servlet整合-Java Web
375 3
|
负载均衡 安全 Java
nacos常见问题之nacos滚动重启时 服务实例大量下线如何解决
Nacos是阿里云开源的服务发现和配置管理平台,用于构建动态微服务应用架构;本汇总针对Nacos在实际应用中用户常遇到的问题进行了归纳和解答,旨在帮助开发者和运维人员高效解决使用Nacos时的各类疑难杂症。